6.5 图的遍历

从已给的连通图中某一顶点出发，沿着一些边访遍图中所有的顶点，且使每个顶点仅被访问一次，就叫做图的遍历，它是图的基本运算。

6.5.1 深度优先遍历DFS：一条道走到黑，不行再退回

  • 如果对非连通图进行深度优先遍历，只需要在遍历某一个连通分量后，在没有访问的结点任取一个开始遍历即可。

6.5.2 广度优先遍历BFS

  • 利用一个队列，从起点开始，每次出队时，把出队元素所有未访问过的邻接点加入队列，直到队列为空。（其实DFS的递归也同样利用了栈）

6.6 图的应用

最小生成树Minimum Spanning Tree

最小生成树:给定一个无向网络在该网的所有生成树中，使得各边权值之和最小的那棵生成树称为该网的最小生成树，也叫最小代价生成树。

最短路径

一、单源最短路径—用Dijkstra(迪杰斯特拉）算法：一次性算出从起点到其他所有点的最短路径

二、所有顶点间的最短路径—用Floyd(弗洛伊德）算法

有向无环图

检测AOV网中是否存在环方法:
对有向图构造其顶点的拓扑有序序列，若网中所有顶点都在它的拓扑有序序列中，则该AOV 网必定不存在环。

关键路径