广度优先搜索(BFS)
之前所讨论的BFS是种“简化的”版本，而“通用的”BFS将作为其他图算法的框架，所以在通用BFS的执行途中需记录一些信息。算法导论中的BFS需要记录顶点颜色(白/灰/黑=未到达/已到达/已到达且所有邻接顶点已到达)。顶点的\(\pi\)为前驱顶点，\(d\)为前驱顶点的\(d+1\)(源点的\(d\)为0)。在这种定义下顶点入队时从白染灰，出队时从灰染黑。BFS结束后利用顶点的\(\pi\)可得到该BFS下源点与其可达顶点形成的BFS树，树中的顶点为黑色而其他未达的顶点为白色。
1 2 3 4 5 6 7 8 9 10 11 12 13 | def bfs(graph,vertex): visited = [vertex,] queue = [vertex,] while queue: vertex = queue.pop(0) for v in graph.getVertices(vertex): if v not in visited: queue.append(v) visited.append(v) print visited |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 | def bfs(graph,vertex): attr = dict() queue = [] for v in graph.vertices(): attr[v] = dict() attr[v]['color'] = 'white' attr[v]['d'] = -1 attr[v]['pi'] = None attr[vertex]['color'] = 'grey' attr[vertex]['d'] = 0 queue.append(vertex) while queue: vertex = queue.pop() for v in graph.getVertices(vertex): if attr[v]['color'] == 'white': attr[v]['color'] = 'grey' attr[v]['d'] = attr[vertex]['d'] +1 attr[v]['pi'] = vertex queue.append(v) attr[vertex]['color'] = 'black' print(attr) |
单源最短路径(无权图)
BFS结束后源点与其可达顶点记录了\(d\)，事实上\(d\)记录了顶点距离源点的最小边数，也就是无权图下的单源最短路径。这个性质必须要保证，因为其关系到BFS的正确性，BFS必须按层次的把第一次访问的顶点染灰，所以顶点应当在距离源点最近的路径(最少的层数)处发生染灰，下面证明关于BFS正确性的命题“BFS结束后源点\(s\)与其所有可达顶点记录的\(d\)为其距源点的最短路径距离值，\(s\)到\(u\)的其中一个最短路径为\(s\)到\(u.\pi\)的其中一个最短路径加上边\((u.\pi,u)\) ”。
1) 把BFS后关于源点s与顶点u的\(d\)计为\(d(s,u)\)，s到u的最少边数计为\(D(s,u)\)，初始顶点的\(d=\infty\);
2) 容易证明若源点s可达u与v且存在边\((u,v)\)，则\(D(s,v) \leq D(s,u) +1\)。利用其证明“从图中任意源点BFS，结束后所有顶点满足\(D\leq d\)”。初始时s被染灰\(D(s,s)=d(s,s)=0\)满足归纳假设，设u染灰时\(D(s,u) \leq d(s,u)\)，然后在u下染灰其邻接顶点v则有\( D(s,v) \leq D(s,u)+1\leq d(s,u)+1 = d(s,v)\)。命题得证。
3) 然后证明命题“BFS队列在任何时刻至多有两种\(d\)值，并且在队列中有两个或以上元素时，队列首尾顶点\(v_{0},v_{-1}\)满足\(d(v_{-1}) \leq d(v_{0})+1\)，且对于有前后关系的任意两个元素而言有\(d(v_{i}) \leq d(v_{i+1})\)”。然后定义每轮BFS是出队一个顶点然后把其所有白色邻接顶点染灰入队，初始时队列\([s]\)满足归纳假设。设某轮有出队顶点但无白色邻接顶点入队，利用不等式很容易得出剩下的队列依然满足归纳假设。然后设某轮有出队顶点且有若干顶点染灰入队，这些新入队的顶点显然都有\(d=d(v’_0)+1\)(\(v’_0\)是已出队的队头)，若此时队列有大于等于两个元素，有\(d=d(v’_0)+1 \leq d(v_0)+1\)，这里新队头\(v_0\)也有可能是新加入的顶点。然后设旧队尾\(v’_{-1}\)未出队，则有\(d(v’_{-1}) \leq d(v’_0)+1 = d\)，不等式其余部分不被影响。这样原命题得证(该讨论忽略一些其他的细节情况)。结合该命题与顶点仅染灰入队至多一次的特性，可得推论“在BFS的整个过程中，对任意两顶点u与v，若u先于v入队则\(d(u) \leq d(v)\)”。
4) 用反证法证明正确性命题。设BFS结束后，取满足\(d(u) \neq D(u)\)的所有顶点中\(D\)最小的其中一个为u，结合(2)可得\(d(u) > D(u)\)。设从源点到u的某最短路径中v为u的前驱，可得\(D(u)=D(v)+1>D(v)\)，根据选择顶点u的方式可得\(D(v)=d(v)\)。整理上述信息得不等式\(d(u)>D(u)=D(v)+1=d(v)+1\)。然后考虑在BFS的某步前驱顶点v出队，v的全部邻接顶点包括u将被访问。若此时u为白色则\(d(u)=d(v)+1\)与不等式矛盾。若此时u为黑色则其已经入队并出队一次，结合(3)可得\(d(u) \leq d(v)\)与不等式矛盾。若此时u为灰色则其必然是被早于v出队的某顶点w染灰，可得\(d(u)-1 = d(w) \leq d(v)\)与不等式矛盾。综上所述“BFS结束后不存在满足\(d \neq D\)的顶点”。
5) 然后结合(4)可证明“所有源点可达的顶点必被访问(染色)”，因为可达顶点的\(D\)必然不为无穷，若顶点未被访问则其\(d\)等于初始值(无穷)，此时导致\(d \neq D\)与(4)的结论矛盾。
6) 最后证明原命题的最后一句。设BFS结束后记录有\(v.\pi=u\)，则\(d(v)=d(u)+1\)，故加上\((u,v)\)边即可。