文档介绍：北京大学暑期课 《ACM/ICPC竞赛训练》
北京大学信息学院 郭炜
guo_******@
课程网页：
最小生成树(MST)问题
本文大量内容引自北京大学信息学院程序设计实****实验班）郑聃崴、
陈国鹏等同学的讲义，在此致谢
图的生成树
在一个连通图G中，如果取它的全部顶点和
一部分边构成一个子图G’，即：
V(G’)=V(G);E(G’) ∈E(G)
若边集E(G’)中的边既将图中的所有顶点连
通又不形成回路，则称子图G’是原图G的一
棵生成树。
一棵含有n个点的生成树，必含有n-1条边。
最小生成树
对于一个连通网（连通带权图，假定每条
边上的权均为大于零的实数）来说，每棵
树的权（即树中所有边的权值总和）也可
能不同
具有权最小的生成树称为最小生成树。
最小生成树
生成树
无向连通图的边的集合
无回路
连接所有的点
最小
所有边的权值之和最小
Prim算法
假设G=(V,E)是一个具有n个顶点的连通网，
T=(U,TE)是G的最小生成树，U,TE初值均为空集。
首先从V中任取一个顶点（假定取v1），将它并入
U中，此时U={v1}，然后只要U是V的真子集(U∈V)，
就从那些一个端点已在T中，另一个端点仍在T外
的所有边中，找一条最短边，设为(vi,vj),其中
vi∈U,vj ∈V-U，并把该边(vi, vj)和顶点vj分别并入T
的边集TE和顶点集U，如此进行下去，每次往生成
树里并入一个顶点和一条边，直到n-1次后得到最
小生成树。
图例
关键问题
每次如何从连接T中和T外顶点的所有边中，找
到一条最短的
1) 如果用邻接矩阵存放图，而且选取最短边的
时候遍历所有点进行选取，则总时间复杂度为
O(V2), V 为顶点个数
2)用邻接表存放图,并使用堆来选取最短边，则
总时间复杂度为O(ElogV)
不加堆的Prim 算法适用于密集图，加堆的适用
于稀疏图
POJ 1258 最小生成树模版题
输入图的邻接矩阵，求最小生成树的总权值
(多组数据）
输入样例：
4
0 4 9 21
4 0 8 17
9 8 0 16
21 17 16 0
输出样例：
28
prioirty_queue实现 Prim + 堆 完成POJ1258
//by Guo Wei
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
const int INFINITE = 1 << 30;
struct Edge
{
int v; //边端点，另一端点已知
int w; //边权值，也用来表示v到在建最小生成树的距离
Edge(int v_ = 0, int w_ = INFINITE):v(v_),w(w_) { }
bool operator <(const Edge & e) const
{
return w > ; //在队列里，边权值越小越优先
}
};
vector< vector <Edge> > G(110); //图的邻接表