在一个具有几个顶点的连通图G中，如果存在子图G'包含G中所有顶点和一部分边，且不形成回路，则称G'为图G的生成树，代价最小生成树则称为最小生成树。
许多应用问题都是一个求无向连通图的最小生成树问题。例如：要在n个城市之间铺设光缆，主要目标是要使这 n 个城市的任意两个之间都可以通信，但铺设光缆的费用很高，且各个城市之间铺设光缆的费用不同；另一个目标是要使铺设光缆的总费用最低。这就需要找到带权的最小生成树。
性质
最小生成树的边数必然是顶点数减一，|E| = |V| - 1。最小生成树不可以有循环。最小生成树不必是唯一的。
Prim算法与Kruskal算法是寻找最小生成树的经典方法。
prim算法：
从单一顶点开始，普里姆算法按照以下步骤逐步扩大树中所含顶点的数目，直到遍及连通图的所有顶点。
输入：一个加权连通图，其中顶点集合为V，边集合为E；初始化：Vnew = {x}，其中x为集合V中的任一节点（起始点），Enew = {}；重复下列操作，直到Vnew= V：在集合E中选取权值最小的边（u, v），其中u为集合Vnew中的元素，而v则不是（如果存在有多条满足前述条件即具有相同权值的边，则可任意选取其中之一）；将v加入集合Vnew中，将（u, v）加入集合Enew中；输出：使用集合Vnew和Enew来描述所得到的最小生成树。
为实现这个算法需要一个辅助数组closedge，来记录Vnew到V-Vnew具有最小权值的边。对于每个顶点vi∈V-Vnew，在辅助数组中存在一个分量closedge[i]，表示vi到Vnew的最小代价边，closedge包括两个域， adjvex表示这条边的顶点，lowcost表示vi到adjvex的权值。当选择新的顶点到Vnew,选择新的边到Enew时，要更新closedge
无向加权图：
Graph
#include <iostream>#include <vector>#include <queue>#define MAXW 1000//定义最大权值using namespace std;template<class T>class Graph//无向加权图{public:Graph();~Graph();void Create();//生成加权图void DFSTraverse(void (*fun)(T));//深度优先遍历void BFSTraverse(void (*fun)(T));//广度优先遍历int LocateVex(T vex);int GetVexnum(){return vexnum;}int GetArcnum(){return arcnum;}int** GetAdjMatrix(){return adjMatrix;}T GetVex(int i){return vexs[i];}private:vector<T> vexs;//顶点数组int** adjMatrix;//邻接矩阵int arcnum;//弧数int vexnum;//顶点数bool *visited;int FirstAdjVex(int v);//v的第一个邻接点int NextAdjVex(int v,int w);//从w开始找v的下个邻接点void DFS(int i,void (*fun)(T));};template<class T>Graph<T>::Graph(){adjMatrix=NULL;arcnum=0;visited=NULL;}template<class T>Graph<T>::~Graph(){for (int i=0;i<vexnum;i++){delete [] adjMatrix[i];}delete adjMatrix;adjMatrix=0;delete [] visited;}template<class T>void Graph<T>::Create(){cout<<"输入顶点数，弧数（以空格隔开）：";cin>>vexnum;cin>>arcnum;adjMatrix=new int*[vexnum];for(int i=0;i<vexnum;i++)adjMatrix[i]=new int[vexnum];for (int i=0;i<vexnum;i++){for(int j=0;j<vexnum;j++)adjMatrix[i][j]=MAXW;//初始化邻接矩阵 }visited=new bool[vexnum];cout<<"输入顶点列，以空格隔开：";for (int i=0;i<vexnum;i++){T temp;cin>>temp;vexs.push_back(temp);//输入顶点 }cout<<"输入一条边依附的顶点及权值（A B 1）:"<<endl;for (int i=0;i<arcnum;i++){T v1,v2;int w;cin>>v1;cin>>v2;cin>>w;int x=LocateVex(v1);int y=LocateVex(v2);adjMatrix[x][y]=w;adjMatrix[y][x]=w;//设置权值}}template<class T>int Graph<T>::LocateVex(T vex){for(int i=0;i<vexnum;i++){if (vexs[i]==vex){return i;}}return -1;}template<class T>int Graph<T>::FirstAdjVex(int v){for (int i=0;i<vexnum;i++){if(adjMatrix[v][i]!=MAXW)return i;}return -1;}template<class T>int Graph<T>::NextAdjVex(int v,int w){for (int i=w+1;i<vexnum;i++){if(adjMatrix[v][i]!=MAXW)return i;}return -1;}template<class T>void Graph<T>::DFS(int i,void (*fun)(T))//从第i个顶点深度优先遍历{visited[i]=true;fun(vexs[i]);for (int w=FirstAdjVex(i);w>=0;w=NextAdjVex(i,w)){if(!visited[w]) DFS(w,fun);}}template<class T>void Graph<T>::DFSTraverse(void (*fun)(T)){for(int i=0;i<vexnum;i++)visited[i]=false;for (int i=0;i<vexnum;i++){if(!visited[i])DFS(i,fun);}}template<class T>void Graph<T>::BFSTraverse(void (*fun)(T)){queue<int> Q;for(int i=0;i<vexnum;i++)visited[i]=false;visited[0]=true;fun(vexs[0]);Q.push(0);//顶点入队while (!Q.empty()){//int v=Q.back();int v=Q.front();// 出队 Q.pop();for(int w=FirstAdjVex(v);w>=0;w=NextAdjVex(v,w)){if(!visited[w]){visited[w]=true;fun(vexs[w]);Q.push(w);//访问后顶点入队}}}}
prim算法：
template<class T>void MinSpanTree_PRIM(Graph<T> &G,T u){//Prim算法，生成最小生成树struct cell{T adjvex;//邻接顶点int lowcost;//最小权值 };cell* closedge=new cell[G.GetVexnum()];//辅助数组int k=G.LocateVex(u);for (int i=0;i<G.GetVexnum();i++){if(i!=k){closedge[i].adjvex=u;closedge[i].lowcost=G.GetAdjMatrix()[k][i];}}closedge[k].lowcost=0;for (int i=1;i<G.GetVexnum();i++){int w=MAXW;for(int j=0;j<G.GetVexnum();j++){if(closedge[j].lowcost<w&&closedge[j].lowcost>0){w=closedge[j].lowcost;k=j;}}//输出路径cout<<endl;cout<<"找到路径："<<closedge[k].adjvex<<"----"<<G.GetVex(k)<<"权值："<<w<<endl;closedge[k].lowcost=0;for(int j=0;j<G.GetVexnum();j++){//更新closedge[j]if (G.GetAdjMatrix()[k][j]<closedge[j].lowcost){closedge[j].adjvex=G.GetVex(k);closedge[j].lowcost=G.GetAdjMatrix()[k][j];}}}}
main：
void printfun(char ch){cout<<ch<<" ";}int main(){Graph<char> G;G.Create();cout<<"深度优先遍历:";G.DFSTraverse(printfun);cout<<endl<<"广度优先遍历：";G.BFSTraverse(printfun);MinSpanTree_PRIM(G,G.GetVex(0));return 1;}
例子：
原图：
运行结果：
