数据结构——克鲁斯卡尔（Kruskal）算法

admin • 2023-05-31 18:56 • C/C++

克鲁斯卡尔算法是求连通网的最小生成树的另一种方法。与普里姆算法不同，它的时间复杂度为O（eloge）（e为边数），适合于求边稀疏的网的最小生成树。克鲁斯卡尔算法从另一途径求网的最小生成树。其基本思想是：假设连通网G，令最小生成树的初始状态为只有n个顶点而无边的非连通图T，概述图中每个顶点自成一个连通分量。在E中选择代价最小的边，若该边依附的顶点分别在T中不同的连通分量上，则将此边加入到T中；否则，舍去此边而选择下一条代价最小的边。说白了，优先先选出全体边里最短的那几条，然后如果各分量还没连起来，就继续选择剩余没被选择的边里最短的，直到全部节点都连接在一起。
以下是数据结构中关于克鲁斯卡尔算法的操作（编程风格参考严蔚敏版数据结构）。

宏定义及头文件

#include<iostream>
#include<stdio.h>
using namespace std; 
typedef char VerTexType; 
typedef int ArcType; 
#define MaxInt 32767 
#define MVNum 100
#define ArcNum 100
#define OK 1
#define ERROR -1
int Vexset[MVNum];//辅助数组表示连通分量 
typedef int status;

图和边集合的声明

typedef struct{
	VerTexType vexs[MVNum] {'A','B','C','D','E','F'};
	ArcType arcs[MVNum][MVNum];
	int vexnum = 6,arcnum = 10;
}AMGraph; 

typedef struct{
	VerTexType Head;//起点 
	VerTexType Tail;//终点
	ArcType lowcast; 
}Edge[ArcNum];

说明：为了测试方便就提前写好了图里节点和边的数据。
edge是记录原始的图里全部边数据（包括起点、终点以及权值）

Kruskal辅助数组Vexset

int Vexset[MVNum];//辅助数组表示连通分量

这里一定要理解好Vexset数组的作用和意义。如果这个理解不好，就像prim算法不理解close数组一样，核心算法就理解不了了。
Vexset是以下标i表示节点，以数组的值表示该点的连通量。
如：Vexset[1] = 0，Vexset[0] = 0.表示B节点和A节点是同一个连通量（B的下标为1，A的下标为0）。

Kruskal核心算法：

void Kruskal(AMGraph &G){
	Edge edge;
	InitailEdge(G,edge);
	sort(G,edge);
//	ShowEdge(G,edge);
	for(int i=0;i<G.vexnum;i++){
		Vexset[i] = i;//每个节点自成一个分量 
	}
	int headi,taili;//边起点的下标、边终点的下标 
	int headt,tailt;//操作连通分量时的中间量 
	for(int i=0;i<G.arcnum;i++){
		headi = LocateVex(G,edge[i].Head); 
		taili = LocateVex(G,edge[i].Tail); 
		headt = Vexset[headi];
		tailt = Vexset[taili];
		if(headt!=tailt){//如果两个点不是同一个连通分量
			cout<<edge[i].Head<<"-"<<edge[i].lowcast<<"-"<<edge[i].Tail<<endl;
			for(int j=0;j<G.vexnum;j++){
				if(Vexset[j]==headt){//合并选出来的两个节点，使其处于同一个连通分量
					Vexset[j] = tailt;
				}
			}
		}
	} 
}

代码执行过程：
1、初始化边集合：把图里全部边加入边集合（集合里边的数量就是图里边的数量）。
2、初始化辅助数组Vexset：每个节点自己属于一个连通量（毕竟刚开始谁都没连接谁是吧）。
3、将边集合按照边权值从小到大排序，让循环操作从小边到大边的顺序进行选择。
4、循环获取每一条边的起点和终点。
5、如果起点和终点不是同一个连通分量，就把两个点连起来（合并连通量）。
6、全部点同属一个连通分量，循环结束。

举例子手推算法过程：

此次选的例子还是书上的例子：

老样子先弄出邻接矩阵：

第一步：初始化边集合

第二步：初始化Vexset集合（每个节点分别代表一个连通分量），ABCDEF下标分别对应012345，所以ABCDEF的连通量分别是012345。

第三步（第二第三步可互换）：边集合按边权值从小到大排序

第四步：大循环获取每一条边，看其两个端点是否是同一个连通量（因为边集合排过序了，每一次选择的肯定是未被选择的边集合里最短的边）。下面是大循环的执行过程：
1)、选出AC（权值为1），此时A和C的连通分量不一样（A是0，C是2），将AC的连通量合并（此处的操作是将A的连通量修改成和C一致），此时A和C连通量都是2；小循环未发现和C变化前连通量相同（0）的其它节点（这一步的目的是找出原来的起点，一起并入边集合中），故无实际操作；
此时的Vexset为｛2，1，2，3，4，5｝。

2)、选出DF（权值为2），此时D和F的连通分量不一样（D是3，F是5），将DF的连通量合并，此时D和F连通量都是5；小循环未发现和D变化前连通量相同（3）的其它节点，故无实际操作；
此时的Vexset为｛2，1，2，5，4，5｝。

3)、选出BE（权值为3），此时BE连通分量不一样（B是1，E是4），将BE连通量合并，此时B和E连通量都是4。小循环未发现和B变化前连通量相同（1）的其它节点，故无实际操作；
此时的Vexset为｛2，4，2，5，4，5｝。

4)、选出CF（权值为4），此时CF的连通量不一样（C是2，F是5），将CF连通量合并，此时C和F连通量都是5。小循环发现和C变化前连通量相同（2）的其它节点A，故将A的连通量也修改成F的连通量（5）；
此时的Vexset为｛5，4，5，5，4，5｝。

5)、选出AD（权值为5），此时AD连通量一样（A是5，D是5），无操作。
6)、选出BC，此时BC连通分量不一样（B是4，C是5），将BC连通量合并，此时B和C连通量都是5。小循环发现和B变化前连通量相同（4）的其它节点E，故将E的连通量也修改成C的连通量（5）；
此时的Vexset为｛5，5，5，5，5，5｝。

往后循环，每个点的连通分量都一致，故均无实际操作，直至循环结束。

运行结果

源代码

#include<iostream>
#include<stdio.h>
using namespace std; 
typedef char VerTexType; 
typedef int ArcType; 
#define MaxInt 32767 
#define MVNum 100
#define ArcNum 100
#define OK 1
#define ERROR -1
int Vexset[MVNum];//辅助数组表示连通分量 
typedef int status;
typedef struct{
	VerTexType vexs[MVNum] {'A','B','C','D','E','F'};
	ArcType arcs[MVNum][MVNum];
	int vexnum = 6,arcnum = 10;
}AMGraph; 

typedef struct{
	VerTexType Head;//起点 
	VerTexType Tail;//终点
	ArcType lowcast; 
}Edge[ArcNum];

status CreateUDN(AMGraph &G){//创建无向图 	
	for(int i=0;i<G.vexnum;i++){
		for(int j=0;j<G.vexnum;j++){
			if(i==j){
				G.arcs[i][j] = 0;
			}else
				G.arcs[i][j] = MaxInt;//初始状态全部节点之间相互不可达
		}
	}
	G.arcs[0][1]=6;G.arcs[0][2]=1;G.arcs[0][3]=5;
	G.arcs[1][2]=5;G.arcs[1][4]=3;
	G.arcs[2][3]=5;G.arcs[2][4]=6;G.arcs[2][5]=4;
	G.arcs[3][5]=2;
	G.arcs[4][5]=6;
	for(int i=0;i<G.vexnum;i++){
		for(int j=i+1;j<G.vexnum;j++){
			if(G.arcs[i][j]!=MaxInt){
				G.arcs[j][i] = G.arcs[i][j];
			} 
		}
	}//矩阵对称 
	return OK; 
}

void ShowGraph(AMGraph G){
	cout<<" ";
	for(int i=0;i<G.vexnum;i++){
		cout<<" "<<G.vexs[i];
	}
	cout<<endl;
	for(int i=0;i<G.vexnum;i++){
		cout<<G.vexs[i]<<" ";
		for(int j=0;j<G.vexnum;j++){
			if(G.arcs[i][j]==MaxInt){
				cout<<"* ";
			}else{
				cout<<G.arcs[i][j]<<" ";
			}
		}
		cout<<endl;
	}
}

int LocateVex(AMGraph G, VerTexType v){
	int i;
	for(i=0;i<G.vexnum;i++){
		if(G.vexs[i]==v){
			return i;
		}
	} 
	return ERROR;
}

VerTexType Transform(AMGraph G, int vn){
	return G.vexs[vn]; 
}

void InitailEdge(AMGraph G,Edge &edge){//初始化边表 
	int arcnum = 0;
	for(int i=0;i<G.vexnum;i++){//纵列为起点 
		for(int j=i+1;j<G.vexnum;j++){//横行为终点 
			if(G.arcs[i][j]!=MaxInt&&G.arcs[i][j]!=0){
				edge[arcnum].Head = Transform(G,i);
				edge[arcnum].Tail = Transform(G,j);
				edge[arcnum].lowcast = G.arcs[i][j];
				arcnum++;
			}
		}
	} 
}

void sort(AMGraph G,Edge &edge){
	VerTexType tv;
	ArcType tl;
	for(int i=0;i<G.arcnum;i++){
		for(int j=0;j<G.arcnum-i-1;j++){
			if(edge[j].lowcast>edge[j+1].lowcast){//直接写对象互换报错，忘记咋互换对象了，这样写有点麻烦，先将就着用吧 ，这个操作不是重点 
				tv = edge[j].Head;
				edge[j].Head = edge[j+1].Head;
				edge[j+1].Head = tv;
				
				tv = edge[j].Tail;
				edge[j].Tail = edge[j+1].Tail;
				edge[j+1].Tail = tv;
				
				tl = edge[j].lowcast;
				edge[j].lowcast = edge[j+1].lowcast;
				edge[j+1].lowcast = tl;
			}
		}
	}
}

void ShowEdge(AMGraph G,Edge edge){
	for(int i=0;i<G.arcnum;i++){
		cout<<edge[i].Head<<"-"<<edge[i].lowcast<<"-"<<edge[i].Tail<<endl;
	}
}

void ShowVexset(AMGraph G){
	for(int i=0;i<G.vexnum;i++){
		cout<<Vexset[i]<<" ";
	} 
	cout<<endl;
}

void Kruskal(AMGraph &G){
	Edge edge;
	InitailEdge(G,edge); 
//	ShowEdge(G,edge);
	sort(G,edge);
//	ShowEdge(G,edge);
	for(int i=0;i<G.vexnum;i++){
		Vexset[i] = i;//每个节点自成一个分量 
	}
	int headi,taili;//边起点的下标、边终点的下标 
	int headt,tailt;//操作连通分量时的中间量 
	for(int i=0;i<G.arcnum;i++){
		headi = LocateVex(G,edge[i].Head); //起点下标 
		taili = LocateVex(G,edge[i].Tail); //终点下标 
		headt = Vexset[headi];//获取起点的连通分量 
		tailt = Vexset[taili];//获取终点的连通分量 
		if(headt!=tailt){//如果两个点不是同一个连通分量
			cout<<edge[i].Head<<"-"<<edge[i].lowcast<<"-"<<edge[i].Tail<<endl;
			for(int j=0;j<G.vexnum;j++){
				if(Vexset[j]==headt){//更新Vexset数组，把改起点的连通分量改成和终点连通分量一致（其实就是合并连通分量） 
					Vexset[j] = tailt;
//					ShowVexset(G);
				}
			}
		}
	} 	
}

int main(){
	AMGraph G;
	CreateUDN(G);
	ShowGraph(G);
	Kruskal(G); 
	return 0;
}

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。

THE END

二维码

【C ++】C++入门知识（二）

< <上一篇

使用Html做一个简单的登陆页面

下一篇>>

搜索内容