Source code for titan_pylib.graph.bfs

 1from typing import Union
 2from collections import deque
 3
 4

[docs]
 5def bfs(
 6    G: list[list[tuple[int, int]]], s: int, inf: Union[int, float] = float("inf")
 7) -> list[Union[int, float]]:
 8    """
 9    Args:
10        G (list[list[tuple[int, int]]]): 隣接リストです。
11        s (int): 始点です。
12        inf (Union[int, float], optional): 無限大です。
13
14    Returns:
15        list[Union[int, float]]: 始点 ``s`` からの距離です。
16    """
17    dist = [inf] * len(G)
18    dist[s] = 0
19    todo = deque([s])
20    while todo:
21        v = todo.popleft()
22        for x, c in G[v]:
23            if dist[x] == inf:
24                dist[x] = dist[v] + c
25                todo.append(x)
26    return dist

27
28

[docs]
29def bfs_path(
30    G: list[list[tuple[int, int]]],
31    s: int,
32    t: int,
33    inf: Union[int, float] = float("inf"),
34) -> tuple[list[int], list[Union[int, float]]]:
35    """
36    Args:
37        G (list[list[tuple[int, int]]]): 隣接リストです。
38        s (int): 始点です。
39        t (int): 終点です。
40        inf (Union[int, float], optional): 無限大です。
41
42    Returns:
43        tuple[list[int], list[Union[int, float]]]: ``s`` から ``t`` へのパスと、 ``s`` からの距離です。
44    """
45    prev = [-1] * len(G)
46    dist = [inf] * len(G)
47    dist[s] = 0
48    todo = deque([s])
49    while todo:
50        v = todo.popleft()
51        for x, c in G[v]:
52            if dist[x] == inf:
53                dist[x] = dist[v] + c
54                prev[x] = v
55                todo.append(x)
56    if dist[t] == inf:
57        return [], dist
58    path = []
59    while prev[t] != -1:
60        path.append(t)
61        t = prev[t]
62    path.append(t)
63    return path[::-1], dist