广度优先搜索
广度优先搜索(BFS)
之前所讨论的BFS是种“简化的”版本,而“通用的”BFS将作为其他图算法的框架,所以在通用BFS的执行途中需记录一些信息。算法导论中的BFS需要记录顶点颜色(白/灰/黑=未到达/已到达/已到达且所有邻接顶点已到达)。顶点的\(\pi\)为前驱顶点,\(d\)为前驱顶点的\(d+1\)(源点的\(d\)为0)。在这种定义下顶点入队时从白染灰,出队时从灰染黑。BFS结束后利用顶点的\(\pi\)可得到该BFS下源点与其可达顶点形成的BFS树,树中的顶点为黑色而其他未达的顶点为白色。
def bfs(graph,vertex):
visited = [vertex,]
queue = [vertex,]
while queue:
vertex = queue.pop(0)
for v in graph.getVertices(vertex):… 阅读全文