广度优先搜索(BFS)

Algorithm

思想：从点 $s$ 开始，探索所有相邻节点，一层一层探索

$L_0=\{s\}$
$L_1$ 是 $s$ 的所有邻居
$L_2$ 是 $L_{1}$ 中所有的点的邻居，但是不包括 $s$
$\cdots$
$L_k$ 是 $L_{k-1}$ 中所有的点的邻居，但是不包括 $L_{0},\cdots,L_{k-1}$ 中的点

color = white表示该点从未被访问过，color = gray 表示该点正在处理中，color = black表示改点已处理完

Example

class Node:
    def __init__(self, value):
        self.value = value
        self.color = 0  # 0-white 1-gray 2-black
        self.d = float('inf')
        self.p = None


nodes = {n: Node(n) for n in ['r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']}
G = {nodes['s']: [nodes['r'], nodes['u'], nodes['v']],
     nodes['r']: [nodes['t'], nodes['w']],
     nodes['t']: [nodes['r'], nodes['u']],
     nodes['u']: [nodes['t'], nodes['s'], nodes['y']],
     nodes['y']: [nodes['u'], nodes['v'], nodes['x']],
     nodes['v']: [nodes['s'], nodes['w']],
     nodes['w']: [nodes['r'], nodes['v'], nodes['x'], nodes['z']],
     nodes['x']: [nodes['w'], nodes['y'], nodes['z']],
     nodes['z']: [nodes['w'], nodes['x']]}


def BFS(graph, start):
    # initialize: done by init Node
    start.color = 1
    start.d = 0
    start.p = None
    queue = [start]
    while queue:
        u = queue.pop(0)
        for v in graph[u]:
            if v.color == 0:
                v.color = 1
                v.d = u.d + 1
                v.p = u
                queue.append(v)
        u.color = 2

BFS(G, nodes['s'])
for n in G.keys():
    print(f"{n.value}:d={n.d}, p={n.p.value if n.p else None}")