[グラフ] 幅優先探索をPythonで実装

Python で幅優先探索を実装します。

キュー

キューにはcollectionsのdequeを使うのでimportします。

deque オブジェクト

import collections

ノードクラス

各ノードは自身の名前、隣接リスト、訪問済みかどうかのフラグを持ちます。

import collections

class Node(object):

    def __init__(self, name):
        self.name = name
        self.adjacency_list = []
        self.visited = False

幅優先探索クラス

疑似コードそのままです。

function 幅優先探索(v)
    Q ← 空のキュー
    v に訪問済みの印を付ける
    v を Q に追加
    while Q が空ではない do
        v ← Q から取り出す
        v を処理する
        for each v に接続している頂点 i do
            if i が未訪問 then
                i に訪問済みの印を付ける
                i を Q に追加

import collections

class Node(object):

    def __init__(self, name):
        self.name = name
        self.adjacency_list = []
        self.visited = False


class BreadthFirstSearch(object):

    def __init__(self):
        self.traversed_order = []

    def search(self, start_node):

        queue = collections.deque()
        start_node.visited = True
        queue.append(start_node)

        while queue:
            current_node = queue.popleft()
            self.traversed_order.append(current_node.name)

            for node in current_node.adjacency_list:
                if not node.visited:
                    node.visited = True
                    queue.append(node)

テスト

下記のグラフでテストします。

ドイツの都市間の接続を示した例

フランクフルトから幅優先検索を行った場合にできる木構造

import collections

class Node(object):

    def __init__(self, name):
        self.name = name
        self.adjacency_list = []
        self.visited = False


class BreadthFirstSearch(object):

    def __init__(self):
        self.traversed_order = []

    def search(self, start_node):

        queue = collections.deque()
        start_node.visited = True
        queue.append(start_node)

        while queue:
            current_node = queue.popleft()
            self.traversed_order.append(current_node.name)

            for node in current_node.adjacency_list:
                if not node.visited:
                    node.visited = True
                    queue.append(node)


if __name__ == '__main__':

    # グラフの生成
    ## ノードの生成
    frankfurt = Node('Frankfurt')
    manheim = Node('Manheim')
    wurzburg = Node('Wurzburg')
    kassel = Node('Kassel')
    karlsruhe = Node('Karlsruhe')
    nurnberg = Node('Nurnberg')
    erfurt = Node('Erfurt')
    munchen = Node('Munchen')
    augsburg = Node('Augsburg')
    shuttgart = Node('Shuttgart')
    ## 隣接リストの生成
    frankfurt.adjacency_list.extend([manheim, wurzburg, kassel])
    manheim.adjacency_list.extend([frankfurt, karlsruhe])
    wurzburg.adjacency_list.extend([frankfurt, nurnberg, erfurt])
    kassel.adjacency_list.extend([frankfurt, munchen])
    karlsruhe.adjacency_list.extend([manheim, augsburg])
    nurnberg.adjacency_list.extend([wurzburg, shuttgart])
    erfurt.adjacency_list.extend([wurzburg])
    munchen.adjacency_list.extend([kassel])
    augsburg.adjacency_list.extend([karlsruhe])
    shuttgart.adjacency_list.extend([nurnberg])

    # 幅探索
    bfs = BreadthFirstSearch()
    bfs.search(frankfurt)
    # ['Frankfurt', 'Manheim', 'Wurzburg', 'Kassel', 'Karlsruhe',
    #  'Nurnberg', 'Erfurt', 'Munchen', 'Augsburg', 'Shuttgart']
    print(bfs.traversed_order)