6/8 图(下)
6.5 图的遍历
从已给的连通图中某一顶点出发,沿着一些边访遍图中所有的顶点,且使每个顶点仅被访问一次,就叫做图的遍历,它是图的基本运算。
6.5.1 深度优先遍历DFS:一条道走到黑,不行再退回
- 如果对非连通图进行深度优先遍历,只需要在遍历某一个连通分量后,在没有访问的结点任取一个开始遍历即可。
6.5.2 广度优先遍历BFS
- 利用一个队列,从起点开始,每次出队时,把出队元素所有未访问过的邻接点加入队列,直到队列为空。(其实DFS的递归也同样利用了栈)
6.6 图的应用
最小生成树Minimum Spanning Tree
最小生成树:给定一个无向网络在该网的所有生成树中,使得各边权值之和最小的那棵生成树称为该网的最小生成树,也叫最小代价生成树。
最短路径
一、单源最短路径—用Dijkstra(迪杰斯特拉)算法:一次性算出从起点到其他所有点的最短路径
二、所有顶点间的最短路径—用Floyd(弗洛伊德)算法
有向无环图
检测AOV网中是否存在环方法:
对有向图构造其顶点的拓扑有序序列,若网中所有顶点都在它的拓扑有序序列中,则该AOV 网必定不存在环。
关键路径
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 ClancyCC!
评论