图论 笔记（一） kruskal算法 求最小生成树

kruskal算法思想： 既每次把权值最小边的点加入到U集合中（当然不能构成环），到最后必然只剩下一颗树，这时说明最小树已经生成完毕

/* kruskal算法 求最小生成树 */
#include <iostream>
#include <algorithm>
#include <vector>

#define ARRAYNUM 6 // 图的顶点数
#define MAXIMUMCOST 999 // 若两个点不相连则距离为这个数
#define N (ARRAYNUM/2)*((ARRAYNUM+1)/2) // 顶点数为ARRAYNUM的图最多有n条边
using namespace std;

struct node
{
int edge;
int a;
int b;
};

bool cmp(node x,node y)
{
return x.edge<y.edge;
}

int main()
{
int map[ARRAYNUM][ARRAYNUM]= // 点的初始化数组
{
{MAXIMUMCOST,6,1,5,MAXIMUMCOST,MAXIMUMCOST},//v1到其他点的距离
{6,MAXIMUMCOST,5,MAXIMUMCOST,3,MAXIMUMCOST},//v2到其他点的距离
{1,5,MAXIMUMCOST,5,6,4}, //v3到其他点的距离
{5,MAXIMUMCOST,5,MAXIMUMCOST,MAXIMUMCOST,2},//v4到其他点的距离
{MAXIMUMCOST,3,6,MAXIMUMCOST,MAXIMUMCOST,6},//v5到其他点的距离
{MAXIMUMCOST,MAXIMUMCOST,4,2,6,MAXIMUMCOST} //v6到其他点的距离
};
vector<node> Edge;
node tempEdge;
int count=0;
int i,j;
for(i=0;i<ARRAYNUM;i++) // 转化成 边集 如果两点之间有边相连，则加入边值以及顶点到 向量Edge中。
{
for(j=i+1;j<ARRAYNUM;j++)
{
if(map[i][j]!=MAXIMUMCOST)
{
tempEdge.edge=map[i][j];
tempEdge.a=i;
tempEdge.b=j;
Edge.push_back(tempEdge);
}
}
}

int turev[ARRAYNUM]={0}; // 是否加入了U集合中 0表示没加入，1表示加入

sort(Edge.begin(),Edge.end(),cmp); // 对边的长度进行排序

vector<node>::iterator iii,iend;
iend=Edge.end();
cout<<"排序后的边情况"<<endl;
for(iii=Edge.begin();iii!=Edge.end();iii++)
{
cout<<"("<<(*iii).a<<","<<(*iii).b<<")="<<(*iii).edge<<endl;
}
cout<<endl<<endl;

iii=Edge.begin(); //从第一条边开始
cout<<"新加入边("<<(*iii).a<<","<<(*iii).b<<")="<<(*iii).edge<<endl;
turev[(*iii).a]=1; // 标记点加入到 U集合中
turev[(*iii).b]=1;

/*
以下是将边加入到U中的过程，分4种情况，这里我们规定之前已经构造好的一棵树标号为1
情况1：新加入边直接并入根树 (分点a,点b)
情况2：新加入的边构成一颗新的子树
情况3：新加入的边并入已存在的子树 (分点a,点b)
情况4：子树并入根树 (分点a,点b)
结果是 最后所有边都并入根树种。
*/

int k=2;
int temp;
int temp1,temp2;
for(i=1;i<ARRAYNUM-1;i++)
{
for(iii=Edge.begin()+1;iii!=Edge.end();iii++)
{
if( turev[(*iii).a]!=1&&turev[(*iii).b]!=1) //新加入的边构造成一颗新的树,或者新加入的边加入到子树中
{
cout<<"新加入边("<<(*iii).a<<","<<(*iii).b<<")="<<(*iii).edge<<endl;
temp1=turev[(*iii).a]; // a,b两点所属子树的标号，0说明是新的
temp2=turev[(*iii).b];
for(i=0;i<ARRAYNUM;i++) //新加入的边并入到子树中 情况3
{
if(turev[i]==temp1) //树的标号已经存在，即加入点到子树 针对点 a
{
turev[(*iii).b]=temp1;
continue;
}

if(turev[i]==temp2) // 针对点 b
{
turev[(*iii).a]=temp2;
continue;
}
}

turev[(*iii).a]=k; //新加入的边部属于任何一棵子树，所以建立一个标号为K的新子树 情况2
turev[(*iii).b]=k;
k++;
}

if( (turev[(*iii).a]==1&&turev[(*iii).b]!=1) ) //新加入的边或者其他树加入到1号树中
{
cout<<"新加入边("<<(*iii).a<<","<<(*iii).b<<")="<<(*iii).edge<<endl;
turev[(*iii).b]=1; // 加入当前的点 情况1 针对点b

temp=turev[(*iii).b]; //子树加入 情况4
for(i=0;i<ARRAYNUM;i++)
{
if(turev[i]==temp)
turev[i]=1;
}
}

if( (turev[(*iii).a]!=1&&turev[(*iii).b]==1) ) //新加入的边或者其他树加入到1号树中
{
cout<<"新加入边("<<(*iii).a<<","<<(*iii).b<<")="<<(*iii).edge<<endl;
turev[(*iii).a]=1; //情况1 针对点a

temp=turev[(*iii).a]; //情况4
for(i=0;i<ARRAYNUM;i++)
{
if(turev[i]==temp)
turev[i]=1;
}
}
}
}
}