定义：
在一个连通图G中，如果取它的全部顶点和一部分边构成一个子图G’ , 即：
V( G ' ) = V( G );
E( G ')∈E( G );
若边集E( G ')中的边既将图中的所有顶点联通又不形成回路（回路：首尾节点相同），则称子图G'是原图G的一颗生成树。
一颗含有n个点的生成树，必含有n-1条边。
具有权最小的生成树称为最小生成树。
归纳：
生成树：
- 无向连通图的边的集合
- 无回路
- 连接所有点最小
- 所有边的权值之和最小
算法：
- prim算法
- kruskal算法
Prim算法实现
.图节点数目为n，正在构造的生成树为T
.维护dis数组，dis[i]表示vi到T的距离
.开始所有的dis[i]=无穷大，T为空集
1.若|T|=n，最小生成树完成。否则取dis[i]最小的不在T中的点vi加入T
2.更新所有与有边相连且不在T中的点vj的dis值：dis[j]=min(dis[j] , w(vi,vj));
3.转到1；
关键问题
.每次如何从连接T中和T外顶点的所有边中，找到一条最短的。
1.如果用邻接矩阵存图，而且选取最短边的时候遍历所有点进行选取，则总时间复杂度为（V²），V为顶点个数。
2.用邻接表存图，并使用堆来选取最短边，则总时间复杂度为O（ElogV）
3.不加堆优化的Prim算法适用于密集图（稠密图），加堆优化的适用于稀疏图。
#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 > e.w; //在队列里，边权值越小越优先 } }; vector< vector <Edge> > G(110); //图的邻接表int HeapPrim(const vector<vector<Edge> > & G, int n) //G是邻接表,n是顶点数目，返回值是最小生成树权值和 { int i,j,k; Edge xDist(0,0); priority_queue<Edge> pq; //存放顶点及其到在建生成树的距离 vector<int> vDist(n); //各顶点到已经建好的那部分树的距离 vector<int> vUsed(n);//标记顶点是否已经被加入最小生成树 int nDoneNum = 0; //已经被加入最小生成树的顶点数目 for( i = 0;i < n;i ++ ) { vUsed[i] = 0; vDist[i] = INFINITE; } nDoneNum = 0; int nTotalW = 0; //最小生成树总权值 pq.push(Edge(0,0)); //开始只有顶点0，它到最小生成树距离0while( nDoneNum < n && !pq.empty() ) { do {//每次从队列里面拿离在建生成树最近的点 xDist = pq.top(); pq.pop(); } while( vUsed[xDist.v] == 1 && ! pq.empty()); if( vUsed[xDist.v] == 0 ) { nTotalW += xDist.w; vUsed[xDist.v] = 1; nDoneNum ++; for( i = 0;i < G[xDist.v].size();i ++ ) {//更新新加入点的邻点 int k = G[xDist.v][i].v; if( vUsed[k] == 0) { int w = G[xDist.v][i].w ; if( vDist[k] > w ) { vDist[k] = w; pq.push(Edge(k,w)); } } } } } if( nDoneNum < n ) return -1; //图不连通 return nTotalW; } 考察了所有的边，且考察一条边时 可能执 行 pq.push(Edge(k,w)) 故复杂度O(ELogV)int main() { int N; while(cin >> N) { for( int i = 0;i < N; ++i) G[i].clear(); for( int i = 0; i < N; ++i) for( int j = 0; j < N; ++j) { int w; cin >> w; G[i].push_back(Edge(j,w)); } cout << HeapPrim(G,N) << endl; } }
Kruskal算法
.假设G=（V，E）是一个具有n个顶点的连通图，T=（U，TE）是G的最小生成树，U=V，TE初值为空。
.将图G中的边按权值从小到大依次选取，若选取的边使生成树不形成回路，则把它并入TE中，若形成回路则将其舍弃，知道TE中包含n-1条边为止，此时T为最小生成树。