1、Prim 算法
以某顶点为起点，逐步找各顶点上最小权值的边来构建最小生成树。
2、Kruskal 算法
直接寻找最小权值的边来构建最小生成树。
比较：
Kruskal 算法主要是针对边来展开，边数少时效率会非常高，所以对于稀疏图有很大的优势。
Prim 算法针对顶点展开，对于稠密图，即边数非常多的情况下会更好。
具体代码如下：
/* Graph.h头文件 */
/*包含图的建立：图的深度优先遍历、图的广度优先遍历*/
/*包含图的最小生成树：Prim 算法、Kruskal 算法*/
#include<iostream>
#include"LinkQueue.h"
#define MAXVEX 100
#define MAXEDGE 100
#define INFINITY 65535
#define TRUE 1
#define FALSE 0
typedef char VertexType;
typedef int EdgeType;
typedef int Boolean;
using namespace std;
/*邻接矩阵方式建立图*/
class MGraph{
public:
VertexType vexs[MAXVEX];
EdgeType arc[MAXVEX][MAXVEX];
int numVertexes,numEdges;
};
/*建立无向网图的邻接矩阵表示*/
void CreateMGraph(MGraph *G)
{
int i,j,k,w;
cout<<"输入顶点数和边数："<<endl;
cin>>G->numVertexes>>G->numEdges;
cin.clear();
cout<<"输入顶点信息："<<endl;
for(i=0;i<G->numVertexes;i++)
{
cin>>G->vexs[i];
cin.clear();
}
for(i=0;i<G->numVertexes;i++)
for(j=0;j<G->numVertexes;j++)
{
if (i==j)
G->arc[i][j]=0;
else
G->arc[i][j]=INFINITY;
}
for(k=0;k<G->numEdges;k++)
{
cout<<"输入边（vi,vj）上的下标i，下标j和权w:"<<endl;
cin>>i>>j>>w;
cin.clear();
G->arc[i][j]=w;
G->arc[j][i]=G->arc[i][j];
}
}
/*邻接矩阵的深度优先递归算法*/
Boolean visited[MAXVEX]; /*访问标志的数组*/
void DFS(MGraph G,int i)
{
int j;
visited[i]=TRUE;
cout<<G.vexs[i]; /*打印顶点，也可以其他操作*/
for(j=0;j<G.numVertexes;j++)
if(G.arc[i][j]==1 && !visited[j])
DFS(G,j); /*对为访问的邻接顶点递归调用*/
}
/*邻接矩阵的深度优先遍历操作*/
void DFSTraverse(MGraph G)
{
cout<<"
深度优先遍历结果为："<<endl;
int i;
for(i=0;i<G.numVertexes;i++)
visited[i]=FALSE; /*初始化所有顶点状态都是未访问过状态*/
for(i=0;i<G.numVertexes;i++)
if(!visited[i]) /*对未访问过的顶点调用DFS，若是连通图，只会执行一次*/
DFS(G,i);
cout<<endl;
}
/*邻接矩阵的广度遍历算法*/
void BFSTraverse(MGraph G)
{
cout<<"广度优先遍历结果为："<<endl;
int i,j;
LinkQueue Q;
for(i=0;i<G.numVertexes;i++)
visited[i]=FALSE;
for(i=0;i<G.numVertexes;i++)
{
if(!visited[i])
{
visited[i]=TRUE;
cout<<G.vexs[i];
Q.EnQueue(i);
while(!Q.QueueEmpty())
{
Q.DeQueue(&i);
for(j=0;j<G.numVertexes;j++)
{
if(G.arc[i][j]==1 && !visited[j])
{
visited[j]=TRUE;
cout<<G.vexs[j];
Q.EnQueue(j);
}
}
}
}
}
cout<<endl;
}
/* Prim算法生成最小生成树 */
void MiniSpanTree_Prim(MGraph G)
{
cout<<"Prim算法生成最小生成树，结果为："<<endl;
int min,i,j,k;
int adjvex[MAXVEX];
int lowcost[MAXVEX];
lowcost[0]=0;
adjvex[0]=0;
for(i=1;i<G.numVertexes;i++)
{
lowcost[i]=G.arc[0][i];
adjvex[i]=0;
}
for(i=1;i<G.numVertexes;i++)
{
min=INFINITY;
j=1;k=0;
while(j<G.numVertexes)
{
if(lowcost[j]!=0 && lowcost[j]<min)
{
min=lowcost[j];
k=j;
}
j++;
}
cout<<"("<<adjvex[k]<<","<<k<<")"<<endl;
lowcost[k]=0;
for(j=1;j<G.numVertexes;j++)
{
if(lowcost[j]!=0 && G.arc[k][j]<lowcost[j])
{
lowcost[j]=G.arc[k][j];
adjvex[j]=k;
}
}
}
cout<<endl;
}
/* Kruskal 算法生成最小生成树 */
class Edge{ /*对边集数组Edge结构的定义*/
public:
int begin;
int end;
int weight;
};
void Swap(Edge *edges,int i,int j) /* 交换权值 以及头和尾 */
{
int temp;
temp=edges[i].begin;
edges[i].begin=edges[j].begin;
edges[j].begin=temp;
temp=edges[i].end;
edges[i].end=edges[j].end;
edges[j].end=temp;
temp=edges[i].weight;
edges[i].weight=edges[j].weight;
edges[j].weight=temp;
}
void sort(Edge edges[],MGraph *G) /* 对权值进行排序 */
{
int i,j;
for ( i=0;i<G->numEdges;i++)
{
for ( j=i+1;j<G->numEdges;j++)
{
if (edges[i].weight>edges[j].weight)
{
Swap(edges,i,j);
}
}
}
cout<<"权排序之后的为:"<<endl;
for (i=0;i<G->numEdges;i++)
{
cout<<"("<<edges[i].begin<<","<<edges[i].end<<")"<<endl;
}
}
int Find(int *parent,int f) /*查找连线顶点的尾部下标*/
{
while (parent[f]>0)
f=parent[f];
return f;
}
void MiniSpanTree_Kruskal(MGraph G)
{
int i,j,n,m;
Edge edges[MAXEDGE];
int parent[MAXVEX];
/*将邻接数组G转化为边集数组edges并按权由小到大排序*******BEGIN*********/
int k=0;
for ( i=0;i<G.numVertexes-1;i++)
{
for (j=i+1;j<G.numVertexes;j++)
{
if (G.arc[i][j]<INFINITY)
{
edges[k].begin=i;
edges[k].end =j;
edges[k].weight=G.arc[i][j];
k++;
}
}
}
sort(edges, &G);
/***************END***********************/
for (i=0;i<G.numVertexes;i++)
parent[i]=0; /* 初始化数组值为0 */
cout<<"Kruskal 算法生成最小生成树，结果为："<<endl;
for (i=0;i<G.numEdges;i++) /* 循环每一条边 */
{
n=Find(parent,edges[i].begin);
m=Find(parent,edges[i].end);
if (n!=m) /* 假如n与m不等，说明此边没有与现有的生成树形成环路 */
{
parent[n]=m; /* 将此边的结尾顶点放入下标为起点的parent中。 */
/* 表示此顶点已经在生成树集合中 */
cout<<"("<<edges[i].begin<<","<<edges[i].end<<") "<<edges[i].weight<<endl;
}
}
}对于如下所示的图：
运行程序，结果如下：
