详解图的应用（最小生成树、拓扑排序、关键路径、最短路径）

可以用连通网来表示n个城市以及n个城市间可能设置的通信线路，其中网的顶点表示城市，边表示两城市之间的线路，赋于边的权值表示相应的代价。即无向连通图的生成树不是唯一的。如果无向连通图是一个网，那么，它的所有生成树中必有一棵边的权值总和最小的生成树，我们称这棵生成树为最小生成树，简称为最小生成树。T ，U的初始状态：令集合U 的初值为U＝{u1}，集合T 的初值为T＝{}。Prim 算法可用下述过程描述，其中用wuv 表示顶点u 与顶点v 边上的权值。为实现Prim 算法，需设置两个辅助closedge，用来保存U到集合V－U 的各个顶点中具有最小权值的边的权值。