[b]このワークシートは[url=https://www.geogebra.org/m/twxxx3yq]Math by Code[/url]の一部です。[br][/b][br][url=https://www.geogebra.org/m/abubej5f]treeで遊ぼう[/url]では、[br]木の頂点を親からスタートして[b]すべてなぞる（traverse)[/b]とき[br]前置、中置、後置という３種類の順番があることを知った。[br]また、探索するには深さ優先と幅優先があることも知ったね。[br][br]今回は、木ではなく[b][color=#0000ff]グラフで、[br]なぞる１方法[/color]、[size=100]深さ優先検索、[br]DepthFirstSearch, DFS[/size][/b]に挑戦してみよう。[br]

[b][size=150]＜隣接のデータ化＞[/size][/b][br][br]dfsを木からグラフに一般化する前に隣接関係をみてみよう。[br][br]点と点が辺でつながっていること、隣接(adjacent)していることを、どう表しますか。[br][br]例えば、V=['a','b','c','d']、E=[('a','b'),('a','c'),('a','d'),('b','c'),('c','d')]のグラフがあるとしよう。[br][br]隣接点セットのリストというやり方が思いつくね。[br]Vの要素ｘの隣接点セット、[b]近傍N(x)を並べたリスト[/b]だ。[br][{'b','c','d'}, # N('a')[br]{'a'}, #N('b')[br]{'a','b'}, #N('c')[br]{'a','c'} #N('d')[br]][br]注意点は頂点a,b,c,dが集合ではなく、リストとして順番を持たせないと、参照がしにくいということだ。[br][br]アクセスしやすさを考えて、[b]頂点をキーにした隣接点辞書[/b]にする方法があります。[br][br][b]{"a":set("bcd"), "b":set("a"), "c":set("ab"),"d":set("ac")}　[br][/b][br]コメントも不要になりますね。[br][br]頂点Vの数が4だから、4×4の行列にして、インデックスをa,b,c,dの順に0,1,2,3とすることで、i行j列に[br]1を立てると連結、0だと非連結とする[b]隣接行列[/b]にすることで、行列操作でグラフを扱うという方向性[br]に進むこともありますね。[br]

＜深さ優先の考え方＞[br]dfsの考え方はわりと簡単で、訪問した点には印をつけておき、[br]同じ点をくり返し訪問しないようにする。[br]だから、簡単にかくと、次のような関数になるね。[br][br][b][color=#0000ff]dfs(u):[br]１．もし、頂点uが訪問済なら終了する。[br]２．そうでないなら、uをたどる。[br]・uは訪問済みに変更する。[br]・uのすべての隣接点vについて、dfs(v)をする。ここで１つ深く進むことになる。[br][/color][/b] [br]しかし、よく考えると問題がある。[br]訪問して行き止まりになったら、さっきいた点は訪問済だから、もとに戻れなくなる。[br][br]だから、同じ深さの探索のレベル上では、[b]再帰で進んだあとの行に、訪問済をキャンセルする操作[/b]、[br]つまり、[b]バックトラック（戻り道）しないと、行き止まりでループしたり、終了してしまう[/b]。[br][br]バックトラックというと、難しそうに感じるひともいるかもしれない。[br]でも、これって、[b]迷路で行き止まりになりそうなとき[/b]は、[br]壁の左がわをさわって進むと同じところに戻ることで、[b]行き止まりからの復帰[/b]、[br][b]戻り道[/b]をしているのと同じイメージだね。[br][br]だから、[br][br]dfs(u):[br]１．もし、頂点uが訪問済なら終了する。[br]２．そうでないなら、uをたどる。[br]・uを訪問済にする[br]・uのすべての隣接点vについて、dfs(v)をする[br][size=150][color=#0000ff][b]３．uの探索が終わっているから、uを未訪問とする。[br][/b][/color][/size][br][color=#9900ff][u][b][size=150]質問：dfsの考え方でグラフの中のpathをさがすにはどうしたらよいでしょうか。[br][/size][/b][/u][/color][br]pathのstartとendを与え、グラフ構造としてのデータgraphを与えます。[br]グラフの各点の訪問済かどうかの記録用の辞書visitedも与えます。[br]また、記録用にpathというリストを参照型で与えましょう。[br]だから、dfsの引数はgraph, start,end,visited,pathで、戻り値はresultです。[br]dfsは[br]1。探索の現在地[b][color=#0000ff]now_pos[/color][/b]での[b]訪問記録に印をつけてpathに追記する[/b]。[br]2。現在地がendについたら[u]pathを返して終了。[/u][br]3。隣接点neighborが訪問済でないなら、深くdfsを再帰的に進む。[br]4。[b][color=#0000ff]now_pos[/color][/b]探索後は訪問記録vの印を消しpathも１つ消し。[u]無しを返す[/u]。[br]入口用の関数find_path(graph,start,end)を作り、dfsが動くために[br]graphという辞書から、訪問記録として辞書を初期化します。[br]たとえば、[br]graph = {[br] "a": ["b", "c"],[br] "b": ["a", "c", "d"],[br] "c": ["a", "b", "e"],[br] "d": ["b"],[br] "e": ["c"][br]}[br]というグラフでは、dfs(a)→dfs(b)でpathにa,bが順調につまれます。[br]ところが、bの辞書の先頭のaは訪問済だから、dfs(c)に進み、path=[a,b,c]となります。[br]次にcの辞書のa,bが訪問済なので、dfs(e)に進み、paht=[a,b,c,e]となりますね。[br]現在地==endなので、このpathを返します。[br][br]このプログラムの特徴は、[br]最短経路を探しているわけではないし、一つ見つかれば終了します。[br]複数見つけることはできませんし、最短でもないのですが、迷路図をデータ化して抜け出す方法を見つけたりするには使えそうですね。[br][br][IN]Python[br]#================================================[br]import networkx as nx[br]from collections import defaultdict[br]from matplotlib import pyplot as plt[br]#ここからPathの検索（深さ優先）[br][b][color=#0000ff]def dfs(graph, now_pos, goal, visited, path):[br] visited[now_pos] = True[br] path.append(now_pos)[br] if now_pos == goal:[br] return path[br] for neighbor in graph[now_pos]:[br] if not visited[neighbor]:[br] result = dfs(graph, neighbor, goal, visited, path.copy())[br] if result:[br] return result[br] visited[now_pos] = False[br] path.pop()[br] return None[br][/color][/b][br]def find_path(graph, start, end):[br] keys=graph.keys()[br] visited={}[br] for item in keys:[br] visited[item]=False[br] path = [][br] return dfs(graph, start, end, visited, path)[br] [br]def solve_path(graph,start,end):[br] #グラフ[br] G = nx.Graph()[br] nodes = graph.keys()[br] edges = [][br] G.add_nodes_from(nodes)[br] for k,v in graph.items():[br] for vi in v:[br] edges.append((k,vi))[br] G.add_edges_from(edges)[br] pos = nx.circular_layout(G)[br] nx.draw_networkx(G)[br] #探索開始[br] result = find_path(graph, start,end)[br] print(result)[br] if result:[br] arrowList=[][br] answer = f"見つかったpathは{result[0]}"[br] for i in range(len(result)-1):[br] arrowList.append((result[i],result[i+1]))[br] answer +=f"->{result[i+1]}"[br] else:[br] answer="パスは見つかりませんでした"[br] return answer[br] [br]# グラフデータと実行[br]graph = {[br] "a": ["b", "c"],[br] "b": ["a", "c", "d"],[br] "c": ["a", "b", "e"],[br] "d": ["b"],[br] "e": ["c"][br]}[br][br]start = "a"[br]end = "e"[br]solve_path(graph,start,end)[br]#=====================================================[br][OUT][br]['a', 'b', 'c', 'e'][br]'見つかったpathはa->b->c->e'

適当なグラフを生成して実験してみよう。[br]頂点数,辺数ともに10として、0から1へのpathを探す。[br]Vs=10[br]Es=10[br]start=0[br]goal=1[br]ad,G = gene_G(Vs,Es)[br]solve_path(ad,start,goal)[br]

今度は、ゴールを決めずにいけるところまで進もう。[br][br][color=#9900ff][b][size=150]質問：ゴールを決めないで探索するにはどうしたらようでしょうか。[br][/size][/b][/color][br]dfsなどで、endやゴールを取り除きます。また、now_pos==goalならpathを返すというのをやめて、[br]進めたらそのつどprint(path)をしよう。[br][br]#ゴールなし[br]import networkx as nx[br]from collections import defaultdict[br]from matplotlib import pyplot as plt[br]#ここからPathの検索（深さ優先）[br]def dfs(graph, now_pos, visited, path):[br] visited[now_pos] = True[br] [b][color=#0000ff] path.append(now_pos)[br] print(path)[br][/color][/b] for neighbor in graph[now_pos]:[br] if not visited[neighbor]:[br] result = dfs(graph, neighbor, visited, path.copy())[br] visited[now_pos] = False[br] path.pop()[br] return None[br][br]def find_path(graph, start):[br] keys=graph.keys()[br] visited={}[br] for item in keys:[br] visited[item]=False[br] path = [][br] return dfs(graph, start, visited, path)[br] [br]def solve_path(graph,start):[br] #グラフ[br] G = nx.Graph()[br] nodes = graph.keys()[br] edges = [][br] G.add_nodes_from(nodes)[br] for k,v in graph.items():[br] for vi in v:[br] edges.append((k,vi))[br] G.add_edges_from(edges)[br] pos = nx.circular_layout(G)[br] nx.draw_networkx(G)[br] #探索開始[br] result = find_path(graph, start)[br] return result[br] [br]# グラフデータと実行[br]graph = {[br] "a": ["b", "c"],[br] "b": ["a", "c", "d"],[br] "c": ["a", "b", "e"],[br] "d": ["b"],[br] "e": ["c"][br]}[br][br]start = "a"[br]solve_path(graph,start)[br]#================================[br][OUT][br]['a'][br]['a', 'b'][br]['a', 'b', 'c'][br]['a', 'b', 'c', 'e'][br]['a', 'b', 'd'][br]['a', 'c'][br]['a', 'c', 'b'][br]['a', 'c', 'b', 'd'][br]['a', 'c', 'e']

スタートもゴールも決めずに調べて、[br]もし全点通過するパスができたら、それはハミルトンパスと言われているね。[br]それをめざして取り組んでみよう。[br][br]スタートを中で回して、パスを共通のところに格納しながらあとで、[br]その経路の通過頂点数がグラフの頂点数と同じになればハミルトンパスといえるね。[br][br]質問：パスを記録しながら最長のパスを表示するにはどんな工夫が必要でしょうか。[br][br]深さ優先のために、dfs関数でどんどん進むがこれ以上すすめなくなったときに[br]最長パスになる可能性がある。[br]だから、むしろ進めなくなったときに作った最長パスpathを[b]prevpath[/b]に保存しておくことで、[br]pathの記録リストpathsに記録できる。dfsに入ったときも、これ以上進めなくなった状態でも,[br]重複をかまわず記録漏れをなくすことを優先してpathsにためこもう。[br][br]dfsの[b]依頼主であるfind_path[/b]にpathsを返すと、たまったpathの最長値maxlenを記録し、[br]maxlenにあてはまる最長のリストを[b]依頼主[/b][b]hamilton_path[/b]に返そう。[br][br]hamilton_pathはnodesの頂点を順にstartにしながらfind_pathの結果をためこみ、すべての頂点の最長パスを比べて、グラフ全体の最長パスを返します。最後に[b]パスを返す前に重複と取り除き、パスの長さが頂点数と同じになるパスならば、ハミルトンパス[/b]というラベルをつけよう。[br][br]#すべての点をスタートにしてなぞる。[br]import networkx as nx[br]from collections import defaultdict[br]from matplotlib import pyplot as plt[br]#ここからPathの検索（深さ優先）[br]def dfs(graph, now_pos, visited, path,[b][color=#0000ff]prevpath,paths[/color][/b]):[br] prevpath = path[br] visited[now_pos] = True[br] path.append(now_pos)[br] [b] paths.append(path)[br][/b] for neighbor in graph[now_pos]:[br] if not visited[neighbor]:[br] dfs(graph, neighbor, visited, path.copy(), prevpath.copy(),paths)[br] else:[br] [b][color=#0000ff]paths.append(prevpath.copy())[/color][br][/b] visited[now_pos] = False[br] path.pop()[br] [b][color=#0000ff] return paths[br][/color][/b][br]def find_path(graph, start):[br] keys=graph.keys()[br] visited={}[br] for item in keys:[br] visited[item]=False[br] path = [][br] prevpath = [][br] paths = [][br] [b] res = dfs(graph, start, visited, path, prevpath,paths)[br] maxlen = max(list(map(lambda x:len(x), res)))[br] fil= list(filter(lambda x:len(x)==maxlen, res))[br] [color=#0000ff]return fil[/color][/b][br][b][color=#0000ff][size=150]def hamilton_path(graph):[br][/size][/color][/b] #グラフ[br] G = nx.Graph()[br] nodes = graph.keys()[br] edges = [][br] G.add_nodes_from(nodes)[br] for k,v in graph.items():[br] for vi in v:[br] edges.append((k,vi))[br] G.add_edges_from(edges)[br] pos = nx.circular_layout(G)[br] nx.draw_networkx(G, node_color='yellow')[br] #探索開始[br] results =[][br] for start in nodes:[br] [b] result = find_path(graph,start)[br][/b] for item in result:[br] results.append(item)[br] #print(results) [br] maxlen = max(list(map(lambda x:len(x), results)))[br] filtered= list(filter(lambda x:len(x) == maxlen, results))[br] unique_list = [][br] for item in filtered:[br] if item not in unique_list:[br] unique_list.append(item)[br] for item in unique_list:[br] if len(item)==len(nodes):[br] comment ="Hamilton Path:"[br] else:[br] comment ="longest Path:"[br] [b][color=#0000ff] print(comment,item)[br][/color][/b] return unique_list[br] [br]# グラフデータと実行[br]graph = {[br] "a": ["b", "c"],[br] "b": ["a", "c", "d"],[br] "c": ["a", "b", "e"],[br] "d": ["b"],[br] "e": ["c"][br]}[br]longest = hamiltorn_path(graph)[br]#===================================================[br][OUT][br]Hamilton Path: ['d', 'b', 'a', 'c', 'e'][br]Hamilton Path: ['e', 'c', 'a', 'b', 'd']

適当に、連結で多重でない単純なグラフをかいて、ハミルトンパスがあるかを探ろう[br][br]#上の続き＝＝＝＝＝＝＝＝＝＝＝＝＝＝[br]import networkx as nx[br]from collections import defaultdict[br]from matplotlib import pyplot as plt[br]import random[br][br]def gene_G(v,e):[br] nodes = [x for x in range(v)] #　0〜v-1のv個の点[br] edges = [] # ランダムにできる辺[br] G = nx.Graph()[br] while len(edges) < e:[br] i,j = random.sample(range(v),2)[br] if i > j: i,j = j,i[br] edges.append((i,j)) #辺の格納[br] G.add_edges_from(edges)[br] G.add_nodes_from(nodes)[br] Ad = nx.[b]to_dict_of_lists[/b](G) #隣接辞書[br] return Ad,G[br][br]Vs=8[br]Es=15[br]ad,G = [b]gene_G[/b](Vs,Es)[br]if nx.[b]is_connected[/b](G):[br] longest = [b]hamiltorn_path[/b](ad)[br]else:[br] print("非連結です")[br]