图的应用¶
最小生成树¶
最小生成树: 带权连通无向图中，所有生成树中权值之和最小的生成树。
Prim算法¶
-
任取一个顶点，去掉所有边
-
选择一个与当前顶点集合距离最近的顶点，并将该顶点和相应的边加进来，同时不能形成回路
-
重复上述步骤，直到所有顶点都被并入为止
Kruskal算法¶
-
去掉所有边
-
选择一条权值最小的边，并将其加入生成树中，同时不能形成回路
-
重复上述步骤，直到所有顶点都被并入为止
最小生成树的性质¶
-
若带权连通无向图的各边权值互不相同，则其最小生成树是唯一的
-
最小生成树的边数等于其顶点数减一
最短路径¶
Dijkstra算法求单源最短路径问题¶
