@@ -0,0 +1,1133 @@
+# -*- coding:utf-8 -*-%0A%0A%0Afrom collections import deque%0Afrom graph import Undigraph%0A%0A%0Adef bfs(graph, s, t):%0A    if s == t:%0A        return %0A    queue = deque()%0A    pre = %5B -1 %5D * len(graph)%0A    visited = %5BFalse%5D * len(graph)%0A    visited%5Bs%5D = True%0A    queue.append(s)%0A    while len(queue) %3E 0:%0A        vertex = queue.popleft()%0A        for adj_v in graph%5Bvertex%5D:%0A            if not visited%5Badj_v%5D:%0A                pre%5Badj_v%5D = vertex%0A                if adj_v == t:%0A                    return pre%0A                visited%5Badj_v%5D = True%0A                queue.append(adj_v)%0A    return pre%0A%0Adef print_vertex_trace(prev, s, t, level=1):%0A    if prev%5Bt%5D != -1 and t != s:%0A        print_vertex_trace(prev, s, prev%5Bt%5D, level+1)%0A    if level == 1:%0A        print(%22%25d%22 %25 t)%0A    else:%0A        print(%22%25d -%3E %22 %25 t, end=%22%22)%0A%0Aif __name__ == '__main__':%0A    g = Undigraph(8)%0A    g.add_edge(0, 1)%0A    g.add_edge(0, 3)%0A    g.add_edge(1, 2)%0A    g.add_edge(1, 4)%0A    g.add_edge(2, 5)%0A    g.add_edge(3, 4)%0A    g.add_edge(4, 5)%0A    g.add_edge(4, 6)%0A    g.add_edge(5, 7)%0A    g.add_edge(6, 7)%0A    print(g)%0A    pre = bfs(g, 0, 7)%0A    print_vertex_trace(pre, 0, 7)%0A

Implement the broad first search of the undirected graph