8  グラフの探索

8.1 幅優先探索

\begin{algorithm} \caption{Breadth-First Search} \begin{algorithmic} \Require A graph $G = (V, E)$ and a source node $s$ \State Create a queue $Q$ \ForAll{$v \in V$} \State $\text{visited}[v] \gets \text{false}$ \EndFor \State $\text{visited}[s] \gets \text{true}$ \State $Q.\text{enqueue}(s)$ \While{$Q$ is not empty} \State $u \gets Q.\text{dequeue}()$ \ForAll{$v \in \text{Adj}(u)$} \If{not $\text{visited}[v]$} \State $\text{visited}[v] \gets \text{true}$ \State $Q.\text{enqueue}(v)$ \EndIf \EndFor \EndWhile \end{algorithmic} \end{algorithm}

8.1.1 Python Implementation

"""
Breadth-First Search for graph traversal.
graph = {
  node: [neighbor1, neighbor2, ...],
    ...
}
"""

from collections import deque

def bfs(graph, start):
    visited = {start}
    queue = deque([start])

    while queue:
        node = queue.popleft()
        print(node)  

        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

if __name__ == "__main__":
    graph = {
        'A': ['B', 'C'],
        'B': ['A', 'D', 'E'],
        'C': ['A', 'F'],
        'D': ['B'],
        'E': ['B'],
        'F': ['C']
    }
    bfs(graph, 'A')

8.2 深さ優先探索

\begin{algorithm} \caption{Depth-First Search} \begin{algorithmic} \Require A graph $G = (V, E)$ and a source node $s$ \State Create a stack $S$ \ForAll{$v \in V$} \State $\text{visited}[v] \gets \text{false}$ \EndFor \State $\text{visited}[s] \gets \text{true}$ \State $S.\text{push}(s)$ \While{$S$ is not empty} \State $u \gets S.\text{pop}()$ \ForAll{$v \in \text{Adj}(u)$} \If{not $\text{visited}[v]$} \State $\text{visited}[v] \gets \text{true}$ \State $S.\text{push}(v)$ \EndIf \EndFor \EndWhile \end{algorithmic} \end{algorithm}

8.2.1 Python Implementation

"""
Depth-First Search for graph traversal.

graph = {
  node: [neighbor1, neighbor2, ...],
    ...
}
"""

def dfs(graph, start):
    visited = {start}
    stack = [start]

    while stack:
        node = stack.pop()
        print(node)  

        for neighbor in reversed(graph[node]):  
            if neighbor not in visited:
                visited.add(neighbor)
                stack.append(neighbor)

if __name__ == "__main__":
    graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F', 'G'],
    'D': ['H', 'I'],
    'E': ['J', 'K'],
    'F': ['L', 'M'],
    'G': ['N', 'O'],
    'H': [], 'I': [], 'J': [], 'K': [],
    'L': [], 'M': [], 'N': [], 'O': []
  }
    dfs(graph, 'A')

8.3 ダイクストラのアルゴリズム

\begin{algorithm} \caption{Dijkstra's Algorithm} \begin{algorithmic} \Require A graph $G = (V, E)$ with non-negative edge weights and a source node $s$ \State $W \gets \emptyset$ \ForAll{$v \in V$} \State $d[v] \gets \infty$ \EndFor \State $d[s] \gets 0$ \While{$W \neq V$} \State $u \gets \text{argmin}_{v \in V \setminus W} d[v]$ \State $W \gets W \cup \{u\}$ \ForAll{$v \in \text{Adj}(u)$} \State $d[v] \gets \min(d[v], d[u] + w(u, v))$ \EndFor \EndWhile \end{algorithmic} \end{algorithm}

"""
Dijkstra's Algorithm for shortest paths in a graph with non-negative edge weights.

graph = {
  node: [(neighbor, weight), ...],
    ...
}
"""

def dijkstra(graph, source):
    dist = {node: float("inf") for node in graph}
    dist[source] = 0

    W = set()

    while W != set(graph):
        # Find the node with the smallest distance
        x = min(
            (node for node in graph if node not in W), 
            key=lambda node: dist[node]
        )

        W.add(x)

        for v, weight in graph[x]:
            if v not in W:
                dist[v] = min(
                  dist[v], 
                  dist[x] + weight)

    return dist


if __name__ == "__main__":

  graph = {
    0: [(1, 2), (2, 1)],
    1: [(2, 3), (3, 3)],
    2: [(4, 1)],
    3: [(5, 2)],
    4: [(3, 2), (5, 5)],
    5: [],
  }

  distances = dijkstra(graph, 0)
  print(distances)