6-6 最小生成树：普利姆算法

构造最小生成树方法（1）：普利姆（Prim）算法

算法思想：

• 设N=(V, E）是连通网，TE是N上最小生成数中边的集合
• 初始令$U=\{u_0\},(u_0\in V), TE=\{ \}$
• 在所有$u\in U,v \in V-U的边(u, v)\in E$中，找一条代价最小的边$(u_0, v_0)$
• 将$(u_0,v_0)$并入集合TE，同时$v_0$并入U
• 重复上述操作直至U=V为止，则T=(V,TE)为N的最小生成树

6-6 最小生成树：克鲁斯卡尔算法

构造最小生成数方法（2）：克鲁斯卡尔（Kruskal）算法

算法思想：

• 设连通网N=(V, E)，令最小生成树初始状态为只有n个顶点而无边的非连通图T=(v,{ })，每个顶点自成一个连通分量
• 在E中选取代价最小的边，若该边依附的顶点落在T中不同的连通分量上（即：不能形成环），则将此边加入到T中；否则，舍去此边，选取下一条代价最小的边
• 依此类推，直至T中所有顶点都在同一连通分量上为止

两种算法比较

6-6 图的应用：最短路径（1）