Python入門: 深さ優先探索(DFS)を使用したグラフ探索

1. 深さ優先探索(DFS)とは

深さ優先探索（DFS: Depth-First Search）は、グラフの探索アルゴリズムの一つで、根から深く（遠く）のノードを優先的に探索する方法です。スタックというデータ構造を用いて実装することが一般的です。

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

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

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

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

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 dfs(self, node, visited=None):
        if visited is None:
            visited = set()
        if node not in visited:
            print(node)
            visited.add(node)
            for neighbor in self.adj_list[node]:
                self.dfs(neighbor, visited)

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.dfs('A')  # or any node

3. DFSの応用例

DFSは様々な問題に応用できます。ここでは、迷路の解決、連結成分の検出、トポロジカルソートの3つを例に挙げます。

3.1 迷路の解決

DFSは迷路問題を解くのにも使われます。ここでは、迷路の入口から出口までの経路を見つける例を示します。

class MazeSolver:
    def __init__(self, maze, start, end):
        self.maze = maze
        self.start = start
        self.end = end
        self.visited = [[False] * len(maze[0]) for _ in range(len(maze))]

    def is_valid(self, pos):
        row, col = pos
        if row < 0 or col < 0 or row >= len(self.maze) or col >= len(self.maze[0]):
            return False
        if self.maze[row][col] == 1 or self.visited[row][col]:
            return False
        return True

    def dfs(self, pos):
        if not self.is_valid(pos):
            return False
        if pos == self.end:
            return True
        self.visited[pos[0]][pos[1]] = True
        rows = [-1, 0, 1, 0]
        cols = [0, 1, 0, -1]
        for i in range(4):
            if self.dfs((pos[0] + rows[i], pos[1] + cols[i])):
                return True
        return False

maze = [
  [0, 0, 0, 0, 0],
  [1, 1, 0, 1, 1],
  [0, 0, 0, 0, 0],
  [1, 0, 1, 1, 1],
  [0, 0, 0, 0, 0]
]
start = (0, 0)
end = (4, 4)
solver = MazeSolver(maze, start, end)
print(solver.dfs(start))  # True or False

3.2 連結成分の検出

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

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 dfs(self, node, visited=None):
        if visited is None:
            visited = set()
        if node not in visited:
            visited.add(node)
            for neighbor in self.adj_list[node]:
                self.dfs(neighbor, visited)
        return visited

    def get_connected_components(self):
        visited = set()
        components = []
        for node in self.nodes:
            if node not in visited:
                component = self.dfs(node)
                components.append(component)
                visited.update(component)
        return components

g = Graph(['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H'])
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.add_edge('G', 'H')
print(g.get_connected_components())  # [{'A', 'B', 'C', 'D', 'E', 'F'}, {'G', 'H'}]

3.3 トポロジカルソート

有向非巡回グラフ（DAG）のノードを順序付けるトポロジカルソートにもDFSは使われます。

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)

    def dfs(self, node, visited, stack):
        visited.add(node)
        for neighbor in self.adj_list[node]:
            if neighbor not in visited:
                self.dfs(neighbor, visited, stack)
        stack.append(node)

    def topo_sort(self):
        visited = set()
        stack = []
        for node in self.nodes:
            if node not in visited:
                self.dfs(node, visited, stack)
        return stack[::-1]  # reverse the list

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

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

AIko Code Symphony