发表于 2018-12-20 | | 次阅读 @TOC 图——应用图广度优先遍历可以判断一个图是否为连通图；广度优先遍历可以求得非带权图的单源最短路径。 最小生成树 Prim算法 Prim算法的时间复杂度为O(|V|^2)，不依赖于|E|，故而适用于求解稠密图的最小生成树。 Kruskal算法 这个算法是按照权值递增的顺序选择合适的边来构造生成树。时间复杂度是O(|E|log|E|) 最短路径 Dijkstra算法求解带权图的单源最短路径问题 Floyd-Warshall算法求解带权图的任意两个顶点之间的最短路径问题 拓扑排序关键路径