Python入門: 幅優先探索(BFS)を使用したグラフ探索

1. 幅優先探索(BFS)とは

幅優先探索（BFS: Breadth-First Search）は、グラフの探索アルゴリズムの一つで、根から近いノードを優先的に探索する方法です。キューというデータ構造を用いて実装することが一般的です。

2. BFSのアルゴリズムとコード例

BFSの基本的なアルゴリズムは以下の通りです。

初期ノードをキューに追加する。
キューが空になるまで以下の操作を繰り返す。
1. キューからノードを一つ取り出す（dequeue）。
2. そのノードが目的のノードなら探索を終了する。
3. そうでなければ、そのノードの隣接ノードのうち未探索のものを全てキューに追加する。

PythonによるBFSのコード例は以下の通りです。

from collections import deque

class Graph:
    def __init__(self, nodes):
        self.nodes = nodes
        self.adj_list = {node: [] for node in nodes}

    def add_edge(self, node1, node2):
        self.adj_list[node1].append(node2)
        self.adj_list[node2].append(node1)

    def bfs(self, start_node):
        visited = set()
        queue = deque([start_node])

        while queue:
            node = queue.popleft()
            if node not in visited:
                print(node)
                visited.add(node)
                queue.extend(self.adj_list[node])

g = Graph(['A', 'B', 'C', 'D', 'E', 'F'])
g.add_edge('A', 'B')
g.add_edge('A', 'C')
g.add_edge('B', 'D')
g.add_edge('B', 'E')
g.add_edge('C', 'F')
g.bfs('A')  # or any node

3. BFSの応用例

BFSは様々な問題に応用できます。ここでは、最短経路探索、連結成分の検出、二部グラフ判定の3つを例に挙げます。

3.1 最短経路探索

BFSは最短経路を見つけるのにも使われます。ここでは、グラフ上での最短経路を見つける例を示します。

from collections import deque

class Graph:
    def __init__(self, nodes):
        self.nodes = nodes
        self.adj_list = {node: [] for node in nodes}

    def add_edge(self, node1, node2):
        self.adj_list[node1].append(node2)
        self.adj_list[node2].append(node1)

    def bfs(self, start_node, end_node):
        visited = {start_node}
        queue = deque([(start_node, [])])

        while queue:
            node, path = queue.popleft()
            visited.add(node)
            path = path + [node]

            if node == end_node:
                return path

            for next_node in self.adj_list[node]:
                if next_node not in visited:
                    queue.append((next_node, path))

        return None

g = Graph(['A', 'B', 'C', 'D', 'E', 'F'])
g.add_edge('A', 'B')
g.add_edge('A', 'C')
g.add_edge('B', 'D')
g.add_edge('B', 'E')
g.add_edge('C', 'F')
print(g.bfs('A', 'F'))  # ['A', 'C', 'F']

3.2 連結成分の検出

グラフがいくつの連結成分に分かれているかを見つけるのにBFSを使うことができます。

from collections import deque

class Graph:
    def __init__(self, nodes):
        self.nodes = nodes
        self.adj_list = {node: [] for node in nodes}

    def add_edge(self, node1, node2):
        self.adj_list[node1].append(node2)
        self.adj_list[node2].append(node1)

    def bfs(self, start_node):
        visited = set()
        queue = deque([start_node])

        while queue:
            node = queue.popleft()
            visited.add(node)

            for next_node in self.adj_list[node]:
                if next_node not in visited:
                    queue.append(next_node)

        return visited

    def get_connected_components(self):
        visited = set()
        connected_components = []

        for node in self.nodes:
            if node not in visited:
                component = self.bfs(node)
                connected_components.append(component)
                visited.update(component)

        return connected_components

g = Graph(['A', 'B', 'C', 'D', 'E', 'F', 'G'])
g.add_edge('A', 'B')
g.add_edge('A', 'C')
g.add_edge('D', 'E')
g.add_edge('F', 'G')
print(g.get_connected_components())  # [{'A', 'B', 'C'}, {'D', 'E'}, {'G', 'F'}]

3.3 二部グラフ判定

BFSは二部グラフを判定するのにも使われます。

from collections import deque

class Graph:
    def __init__(self, nodes):
        self.nodes = nodes
        self.adj_list = {node: [] for node in nodes}

    def add_edge(self, node1, node2):
        self.adj_list[node1].append(node2)
        self.adj_list[node2].append(node1)

    def is_bipartite(self):
        color = {}
        for node in self.nodes:
            if node not in color:
                queue = deque([node])
                color[node] = 0
                while queue:
                    node = queue.popleft()
                    for neighbor in self.adj_list[node]:
                        if neighbor not in color:
                            color[neighbor] = 1 - color[node]
                            queue.append(neighbor)
                        elif color[neighbor] == color[node]:
                            return False
        return True

g = Graph(['A', 'B', 'C', 'D'])
g.add_edge('A', 'B')
g.add_edge('B', 'C')
g.add_edge('C', 'D')
g.add_edge('D', 'A')
print(g.is_bipartite())  # True

以上、幅優先探索(BFS)を使用したグラフ探索の基本的な理解と応用例について学びました。これからBFSを用いた様々な問題解決にチャレンジしてみてください。

AIko Code Symphony