読者です 読者をやめる 読者になる 読者になる

アルゴリズム - PythonでDFSとBFSを書いてみた

python

アルゴリズムの勉強で、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_findedフラグをFalseに戻すことをしていないけど、サンプルですので
def __logging(visited, rest=[]):
    if rest:
        print "visited:%s\n   rest:%s\n" % (visited, rest)
    else:
        print "visited:%s" % (visited)


is_finded = False


def dfs_rec(graph, start, end, visited=[]):
    global is_finded
    if is_finded:
        return visited
    if start == end:
        is_finded = 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も同様。