§06 图状结构

最小生成树

用 n-1 条边连通全部 n 个顶点且总权最小的树，就是最小生成树（MST）。Prim 从一个顶点逐步扩张树，Kruskal 把边按权从小到大挑选、成环即弃。观察边权数字与颜色变化，对比两种算法的贪心策略。

最小生成树

第 01 / 11 步

带权无向图共 5 个顶点、7 条边。目标：用 4 条边连通全部顶点并使总权最小。

伪代码


				
					
					1
					procedure Prim(G, v0)
				
			
				
					
					2
					  T ← {v0}                          // 树中只含起点
				
			
				
					
					3
					  while |T| < n do                  // 树尚未包含全部顶点
				
			
				
					
					4
					    从连接 T 与 V-T 的边中选权最小的边 (u, v)
				
			
				
					
					5
					    T ← T ∪ {(u, v), v}             // 把边和端点并入树
				
			
				
					
					6
					  end while
				
			
				
					
					7
					end procedure

01 / 11

速度