深さ優先探索(DFS)
今回は深さ優先探索(DFS)をやっていきます。
問題は下記URLのを使います
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_11_B&lang=ja
n=int(input()) Graph=[list(map(int, input().split())) for _ in range(n)] start=[0]*(n)#頂点の発見時刻を格納 finish=[0]*(n)#頂点の完了時刻を格納 visit=[False]*(n)#その頂点を訪れたか num=0#現在の時刻
とりあえず、ここまでは入力の部分になります。
肝心の処理を書いていきます
def dfs(vertex): global num num+=1#時刻を進める start[vertex]=num#頂点vertexの発見時刻 visit[vertex]=True#頂点vertexを訪問済みにする for i in Graph[vertex][2:]:#繋がっている頂点を訪れる if(visit[i-1]):#すでに訪れていたらスルー continue dfs(i-1)#再帰的にその頂点に訪れる num+=1#時刻を進める #頂点vertexの完了時刻 finish[vertex]=num if __name__ == "__main__": dfs(0) for i in range(n): print(i+1,start[i],finish[i])
深さ優先探索(DFS)を簡単に説明すると、一本の道を行き止まりまで突き進んで、行き止まりまでいったら分かれ道まで戻ってまた行き止まりまで行くを繰り返すアルゴリズムです。
以下の画像を見ると入力例1はまっすぐなのでいって戻ってくればいいだけ
入力例2のグラフが問題のサイトに乗っているのでそれを見ると深さ優先探索がどのような順番で探索しているのかがわかりやすいと思う。
コード全体
n=int(input()) Graph=[list(map(int, input().split())) for _ in range(n)] start=[0]*(n)#頂点の発見時刻を格納 finish=[0]*(n)#頂点の完了時刻を格納 visit=[False]*(n)#その頂点を訪れたか num=0#現在の時刻 def dfs(vertex): global num num+=1#時刻を進める start[vertex]=num#頂点vertexの発見時刻 visit[vertex]=True#頂点vertexを訪問済みにする for i in Graph[vertex][2:]:#繋がっている頂点を訪れる if(visit[i-1]):#すでに訪れていたらスルー continue dfs(i-1)#再帰的にその頂点に訪れる num+=1#時刻を進める #頂点vertexの完了時刻 finish[vertex]=num if __name__ == "__main__": dfs(0) for i in range(n): print(i+1,start[i],finish[i])
特に難しくはなかったです
