グラフ探索

graph_traversal.py

from collections import deque

graph = {
    "A": ["B", "C"],
    "B": ["A", "D"],
    "C": ["A", "D", "E"],
    "D": ["B", "C", "F"],
    "E": ["C", "F"],
    "F": ["D", "E"],
}


def bfs(start):
    """Shortest number of edges from start to every reachable vertex."""
    dist = {start: 0}
    queue = deque([start])
    while queue:
        node = queue.popleft()
        for nxt in graph[node]:
            if nxt not in dist:
                dist[nxt] = dist[node] + 1
                queue.append(nxt)
    return dist


def dfs(start):
    """Vertices in depth-first visiting order."""
    order, seen = [], set()

    def visit(node):
        seen.add(node)
        order.append(node)
        for nxt in graph[node]:
            if nxt not in seen:
                visit(nxt)

    visit(start)
    return order


print(bfs("A"))  # {'A': 0, 'B': 1, 'C': 1, 'D': 2, 'E': 2, 'F': 3}
print(dfs("A"))  # ['A', 'B', 'D', 'C', 'E', 'F']

python graph_traversal.py