kruscal算法:
对每条边的权值进行从小到大排序,然后从小到大取权值最小的边,如取出的边会在树中产生回路则舍去,取下一条;若不会产生回路则加入到树中。
判断是否会产生回路的方法为:在初始状态下给每个顶点赋予不同的标记,对于遍历过程的每条边,其都有两个顶点,判断这两个顶点的标记是否一致,如果一致,说明它们本身就处在一棵树中,如果继续连接就会产生回路;如果不一致,说明它们之间还没有任何关系,可以连接,同时连接后会将其顶点标记改变。
#include <iostream>
#include <algorithm>
using namespace std;
#define INF 10000
struct AGraph
{
int edges[100][100];
int vertex_num;
};
typedef struct
{
int vertex1,vertex2;
int weight;
}Edge;
bool cmp (Edge a,Edge b)
{
return a.weight < b.weight;
}
void Kruskal(AGraph g)//Kruskal算法
{
int i,j,k,u1,v1,sn1,sn2;
int vset[1000];
Edge E[1000];//存放图中的所有边
k=0;//e数组的下标从0开始计
for(i=0;i<g.vertex_num; i++)//由g产生边集E,不重复选取同一条边
for(j=0;j<=i;j++)
{
if(g.edges[i][j]!=0&&g.edges[i][j]!=INF)
{
E[k].vertex1=i;E[k].vertex2=j;
E[k].weight=g.edges[i][j];
k++;
}
}
sort(E,E+k,cmp);
for(i=0;i<g.vertex_num; i++)//初始化辅助数组
vset[i]=i;
k=1;//k表示当前构造生成树的第几条边,初值为1
j=0;//E中边的下标,初值为0
while(k<g.vertex_num)//生成的边数小于n时循环
{
u1=E[j].vertex1;v1=E[j].vertex2;//取一条边的两个顶点
sn1=vset[u1];
sn2=vset[v1];//分别得到两个边所属的集合编号
if(sn1!=sn2)//两顶点属于不同的集合,该边是最小生成树的一条边
{
cout<<"v"<<u1<<" and v"<<v1<<" to the weight -----"<<(E[j].weight)<<endl;
k++;//生成边数增1
for(i=0;i<g.vertex_num; i++)//两个集合统一编号
if(vset[i]==sn2)//集合编号为sn2的改为sn1
vset[i]=sn1;
}
j++;//扫描下一条边
}
}
int main()
{
int i,j;
AGraph G;
G.vertex_num=6;
for(i=0;i<=5;i++)
for(j=0;j<=5;j++){
if(i==j) G.edges[i][j]=0;
else G.edges[i][j]=INF;
}
G.edges[0][1]= G.edges[1][0]=5;
G.edges[0][2]= G.edges[2][0]=8;
G.edges[0][3]= G.edges[3][0]=7;
G.edges[0][5]= G.edges[5][0]=3;
G.edges[1][2]= G.edges[2][1]=4;
G.edges[2][3]= G.edges[3][2]=5;
G.edges[2][5]= G.edges[5][2]=9;
G.edges[3][4]= G.edges[4][3]=5;
G.edges[3][5]= G.edges[5][3]=6;
G.edges[4][5]= G.edges[5][4]=1;
cout<<"克鲁斯卡尔算法所求的最小生成树为"<<endl;
Kruskal(G);
}