アルゴリズム - PythonでDFSとBFSを書いてみた
アルゴリズムの勉強で、DFS(深さ優先探索)とBFS(幅優先探索)を書いてみました。
サンプルケースでは動いているけど、これで間違いないかはそこまで自信ない。
DFS(非再帰版)
- コード
def __logging(visited, rest=[]): if rest: print "visited:%s\n rest:%s\n" % (visited, rest) else: print "visited:%s" % (visited) def dfs(graph, start, end): stack = [start] visited = [] while stack: label = stack.pop(0) if label == end: visited.append(label) __logging(visited, stack) return visited if label not in visited: visited.append(label) stack = graph.get(label, []) + stack __logging(visited, stack) return visited if __name__ == '__main__': """ +-------------1 | | | +-------+-----+ | | | | | +-2-+ 6 +-8-+ | | | | | | | 3 4 7 9 10 | | | | | +-------5 +---+ 11 """ graph = {1: [2, 6, 8], 2: [3, 4], 3: [], 4: [5], 5: [1], 6: [7], 7: [], 8: [9, 10], 9: [7], 10: [11], 11: [], } print dfs(graph, 1, 10)
- 出力結果
visited:[1] rest:[2, 6, 8] visited:[1, 2] rest:[3, 4, 6, 8] visited:[1, 2, 3] rest:[4, 6, 8] visited:[1, 2, 3, 4] rest:[5, 6, 8] visited:[1, 2, 3, 4, 5] rest:[1, 6, 8] visited:[1, 2, 3, 4, 5] rest:[6, 8] visited:[1, 2, 3, 4, 5, 6] rest:[7, 8] visited:[1, 2, 3, 4, 5, 6, 7] rest:[8] visited:[1, 2, 3, 4, 5, 6, 7, 8] rest:[9, 10] visited:[1, 2, 3, 4, 5, 6, 7, 8, 9] rest:[7, 10] visited:[1, 2, 3, 4, 5, 6, 7, 8, 9] rest:[10] visited:[1, 2, 3, 4, 5, 6, 7, 8, 9, 10] [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
DFS(再帰版)
- コード
- 「見つかったんでもう探索不要」を示すためにフラグ置いたけどダサい
- is_foundフラグをFalseに戻すことをしていないけど、サンプルですので
def __logging(visited, rest=[]): if rest: print "visited:%s\n rest:%s\n" % (visited, rest) else: print "visited:%s" % (visited) is_found = False def dfs_rec(graph, start, end, visited=[]): global is_found if is_found: return visited if start == end: is_found = True visited.append(start) __logging(visited) return visited visited.append(start) __logging(visited) for label in graph.get(start, []): if not label in visited: visited = dfs_rec(graph, label, end, visited) return visited if __name__ == '__main__': """ +-------------1 | | | +-------+-----+ | | | | | +-2-+ 6 +-8-+ | | | | | | | 3 4 7 9 10 | | | | | +-------5 +---+ 11 """ graph = {1: [2, 6, 8], 2: [3, 4], 3: [], 4: [5], 5: [1], 6: [7], 7: [], 8: [9, 10], 9: [7], 10: [11], 11: [], } print dfs_rec(graph, 1, 10)
- 出力結果
visited:[1] visited:[1, 2] visited:[1, 2, 3] visited:[1, 2, 3, 4] visited:[1, 2, 3, 4, 5] visited:[1, 2, 3, 4, 5, 6] visited:[1, 2, 3, 4, 5, 6, 7] visited:[1, 2, 3, 4, 5, 6, 7, 8] visited:[1, 2, 3, 4, 5, 6, 7, 8, 9] visited:[1, 2, 3, 4, 5, 6, 7, 8, 9, 10] [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
BFS
- コード
# -*- coding: utf-8 -*- def __logging(visited, rest=[]): print "visited:%s\n rest:%s\n" % (visited, rest) def bfs(graph, start, end): queue = [start] visited = [] while queue: label = queue.pop(0) if label == end: visited.append(label) __logging(visited, queue) return visited if label not in visited: visited.append(label) queue += graph.get(label, []) #こっちでもいい #queue += [x for x in graph.get(label, []) if x not in visited] __logging(visited, queue) return visited if __name__ == '__main__': """ +-------------1 | | | +-------+-----+ | | | | | +-2-+ 3 +-4-+ | | | | | | | 5 6 7 8 9 | | | | | +-------10 +---+ 11 """ graph = {1: [2, 3, 4], 2: [5, 6], 3: [7], 4: [8, 9], 5: [], 6: [10], 7: [], 8: [7], 9: [11], 10: [1], 11: [], } print bfs(graph, 1, 10)
- 出力結果
visited:[1] rest:[2, 3, 4] visited:[1, 2] rest:[3, 4, 5, 6] visited:[1, 2, 3] rest:[4, 5, 6, 7] visited:[1, 2, 3, 4] rest:[5, 6, 7, 8, 9] visited:[1, 2, 3, 4, 5] rest:[6, 7, 8, 9] visited:[1, 2, 3, 4, 5, 6] rest:[7, 8, 9, 10] visited:[1, 2, 3, 4, 5, 6, 7] rest:[8, 9, 10] visited:[1, 2, 3, 4, 5, 6, 7, 8] rest:[9, 10, 7] visited:[1, 2, 3, 4, 5, 6, 7, 8, 9] rest:[10, 7, 11] visited:[1, 2, 3, 4, 5, 6, 7, 8, 9, 10] rest:[7, 11] [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
補足
BFSのコードにコメント書いてありますが、「子のノード」を取るときに「まだ探索していない子」に絞ってもよし。
queue += [x for x in graph.get(label, []) if x not in visited]
コードには書いていないけどDFSも同様。