bfs

ソースコード

from titan_pylib.graph.bfs import bfs
from titan_pylib.graph.bfs import bfs_path

view on github

展開済みコード

 1# from titan_pylib.graph.bfs import bfs
 2from typing import Union
 3from collections import deque
 4
 5
 6def bfs(
 7    G: list[list[tuple[int, int]]], s: int, inf: Union[int, float] = float("inf")
 8) -> list[Union[int, float]]:
 9    """
10    Args:
11        G (list[list[tuple[int, int]]]): 隣接リストです。
12        s (int): 始点です。
13        inf (Union[int, float], optional): 無限大です。
14
15    Returns:
16        list[Union[int, float]]: 始点 ``s`` からの距離です。
17    """
18    dist = [inf] * len(G)
19    dist[s] = 0
20    todo = deque([s])
21    while todo:
22        v = todo.popleft()
23        for x, c in G[v]:
24            if dist[x] == inf:
25                dist[x] = dist[v] + c
26                todo.append(x)
27    return dist
28
29
30def bfs_path(
31    G: list[list[tuple[int, int]]],
32    s: int,
33    t: int,
34    inf: Union[int, float] = float("inf"),
35) -> tuple[list[int], list[Union[int, float]]]:
36    """
37    Args:
38        G (list[list[tuple[int, int]]]): 隣接リストです。
39        s (int): 始点です。
40        t (int): 終点です。
41        inf (Union[int, float], optional): 無限大です。
42
43    Returns:
44        tuple[list[int], list[Union[int, float]]]: ``s`` から ``t`` へのパスと、 ``s`` からの距離です。
45    """
46    prev = [-1] * len(G)
47    dist = [inf] * len(G)
48    dist[s] = 0
49    todo = deque([s])
50    while todo:
51        v = todo.popleft()
52        for x, c in G[v]:
53            if dist[x] == inf:
54                dist[x] = dist[v] + c
55                prev[x] = v
56                todo.append(x)
57    if dist[t] == inf:
58        return [], dist
59    path = []
60    while prev[t] != -1:
61        path.append(t)
62        t = prev[t]
63    path.append(t)
64    return path[::-1], dist

仕様

bfs(G: list[list[tuple[int, int]]], s: int, inf: int | float = inf) → list[int | float][source]
Parameters:

  • G (list[list[tuple[int, int]]]) – 隣接リストです。

  • s (int) – 始点です。

  • inf (Union[int, float], optional) – 無限大です。

Returns:

始点 s からの距離です。

Return type:

list[Union[int, float]]

bfs_path(G: list[list[tuple[int, int]]], s: int, t: int, inf: int | float = inf) → tuple[list[int], list[int | float]][source]
Parameters:

  • G (list[list[tuple[int, int]]]) – 隣接リストです。

  • s (int) – 始点です。

  • t (int) – 終点です。

  • inf (Union[int, float], optional) – 無限大です。

Returns:

s から t へのパスと、 s からの距離です。

Return type:

tuple[list[int], list[Union[int, float]]]