最小生成树-Prime算法
最小生成树(Minimum Spanning Tree, MST)中的 Prim 算法详解(C语言实现) 1. 什么是最小生成树? 在学习 Prim 算法之前,我们首先需要理解什么是最小生成树(Minimum Spanning Tree,MST)。 1.1 图的基本概念 图(Graph)通常表示为: \[ G=(V,E) \]其中: V:顶点集合(Vertex) E:边集合(Edge) 例如: 2 A ------- B | \ | 6 | \3 | 1 | \ | C ------- D 4 顶点集合: V={A,B,C,D} 边集合: E={(A,B),(A,C),(A,D),(B,D),(C,D)} 如果每条边具有一个权值,那么这个图称为: 带权无向图(Weighted Undirected Graph) 例如: A-B = 2 A-C = 6 A-D = 3 B-D = 1 C-D = 4 2. 什么是生成树? 对于一个连通图,如果选择其中一部分边,使其满足: 包含所有顶点 任意两个顶点之间都有路径 不存在环 那么得到的子图称为: ...