算法系列(BFS DFS).docVIP

4、教你通透彻底理解：BFS和DFS优先有哪些信誉好的足球投注网站算法 ? ?作者：July??二零一一年一月一日 --------------------------------- 本人参考：算法导论?本人声明：个人原创，转载请注明出处。 ok，开始。 翻遍网上，关于此类BFS和DFS算法的文章，很多。但，都说不出个所以然来。读完此文，我想，你对图的广度优先有哪些信誉好的足球投注网站和深度优先有哪些信誉好的足球投注网站定会有个通通透透，彻彻底底的认识。 --------------------- 咱们由BFS开始：首先，看下算法导论一书关于 此BFS 广度优先有哪些信誉好的足球投注网站算法的概述。算法导论第二版，中译本，第324页。广度优先有哪些信誉好的足球投注网站（BFS）在Prime最小生成树算法，和Dijkstra单源最短路径算法中，都采用了与BFS 算法类似的思想。 //u 为 v 的先辈或父母。BFS(G, s)?1? for each vertex u V [G] - {s}?2?????? do color[u] ← WHITE?3????????? d[u] ← ∞?4????????? π[u] ← NIL? //除了源顶点s之外，第1-4行置每个顶点为白色，置每个顶点u的d[u]为无穷大，? //置每个顶点的父母为NIL。?5? color[s] GRAY? //第5行，将源顶点s置为灰色，这是因为在过程开始时，源顶点已被发现。?6? d[s] 0?????? //将d[s]初始化为0。?7? π[s] NIL???? //将源顶点的父顶点置为NIL。?8? Q ??9? ENQUEUE(Q, s)?????????????? ? ?//入队? //第8、9行，初始化队列Q，使其仅含源顶点s。 10? while Q ≠ ?11????? do u DEQUEUE(Q)??? //出队? //第11行，确定队列头部Q头部的灰色顶点u，并将其从Q中去掉。12???????? for each v Adj[u]??????? //for循环考察u的邻接表中的每个顶点v13???????????? do if color[v] = WHITE14?????????????????? then color[v] GRAY???? //置为灰色15??????????????????????? d[v] d[u] + 1???? //距离被置为d[u]+116??????????????????????? π[v] u??????????? //u记为该顶点的父母17??????????????????????? ENQUEUE(Q, v)??????? //插入队列中18???????? color[u] BLACK????? //u 置为黑色 ? ? 由下图及链接的演示过程，清晰在目，也就不用多说了：? 广度优先遍历演示地址： /SFXX/sf1/gdyxbl.html -----------------------------------------------------------------------------------------------------------------ok，不再赘述。接下来，具体讲解深度优先有哪些信誉好的足球投注网站算法。深度优先探索算法 DFS?//u 为 v 的先辈或父母。DFS(G)1? for each vertex u V [G]2?????? do color[u] ← WHITE3????????? π[u] ← NIL//第1-3行，把所有顶点置为白色，所有π 域被初始化为NIL。4? time 0?????? //复位时间计数器5? for each vertex u V [G]6?????? do if color[u] = WHITE7???????????? then DFS-VISIT(u)? //调用DFS-VISIT访问u，u成为深度优先森林中一棵新的树?? ?//第5-7行，依次检索V中的顶点，发现白色顶点时，调用DFS-VISIT访问该顶点。? ? //每个顶点u 都对应于一个发现时刻d[u]和一个完成时刻f[u]。DFS-VISIT(u)1? color[u] GRAY??????????? //u 开始时被发现，置为白色2? time time +1???????????? //time 递增3? d[u] -time?????????????????? //记录u被发现的时间4? for each v Adj[u]?? //检查并访问 u 的每一个邻接点 v5?????? do if color[v] = WHITE??????