第六章算法6.9-克鲁斯卡尔算法

#pragma once
#include 
#include 

using namespace std;

//图的邻接矩阵存储
//表示极大值
#define MaxInt 32767
//最大顶点数
#define MVNum 100
//顶点类型
typedef char VerTexType;
//边上的权值类型
typedef int ArcType;

typedef struct
{
	//顶点表
	VerTexType vexs[MVNum];
	//邻接矩阵
	ArcType arcs[MVNum][MVNum];
	//图中当前顶点数和边数
	int vexnum, arcnum;
}AMGraph;

//辅助数组Edges的定义
struct Edges{
	VerTexType Head;//边的始点					
	VerTexType Tail;//边的终点				
	ArcType lowcost;//边上的权值					
}Edge[(MVNum * (MVNum - 1)) / 2];

//辅助数组Vexset的定义
int Vexset[MVNum];

//自己定义的排序规则 
int cmp(Edges &s1, Edges& s2)
{
	return s1.lowcost < s2.lowcost;

}


//图G中查找顶点u，返回下标；不存在返回-1
int LocateVex(AMGraph G, VerTexType v)
{
	int i;
	for (i = 0; i < G.vexnum; i++)
	{
		if (v == G.vexs[i])
		{
			return i;
		}

	}
}

void CreateUDN(AMGraph& G)
{
	VerTexType v1, v2;
	ArcType w;
	int row;
	int col;
	//输入总顶点数，总边数
	cout << "请输总顶点数：";
	cin >> G.vexnum;
	cout << "请输总边数：";
	cin >> G.arcnum;
	//依次输入点的信息
	for (int i = 0; i < G.vexnum; i++)
	{
		cout << "输入顶点：";
		cin >> G.vexs[i];
	}
	//初始化邻接矩阵，边的权值置为最大值MaxInt
	for (int m = 0; m < G.vexnum; m++)
	{
		for (int n = 0; n < G.vexnum; n++)
		{
			G.arcs[m][n] = MaxInt;
		}
	}
	//构造邻接矩阵
	for (int k = 0; k < G.arcnum; k++)
	{
		cout << "输入边依附的顶点以及权值：";
		cin >> v1 >> v2 >> w;
		row = LocateVex(G, v1);
		col = LocateVex(G, v2);
		G.arcs[row][col] = w;
		G.arcs[col][row] = G.arcs[row][col];
		Edge[k].lowcost = w;
		Edge[k].Head = v1;
		Edge[k].Tail = v2;
	}
}



//输出无向网的邻接矩阵
void ShowGraph(AMGraph G)
{
	cout << "无向网的邻接矩阵为:" << endl;
	for (int i = 0; i < G.vexnum; i++)
	{
		for (int j = 0; j < G.vexnum; j++)
		{
			if (G.arcs[i][j] == MaxInt)
			{
				cout << "∞" << " ";
			}
			else
			{
				cout << G.arcs[i][j] << " ";
			}

		}
		cout << endl;
	}

}


//无向网G以邻接矩阵形式存储，构造G的最小生成树T，输出T的各条边
void MiniSpanTree_Kruskal(AMGraph G)
{
	//将数组Edge中的元素按权值从小到大排序 
	sort(Edge, Edge + G.arcnum, cmp);
	//辅助数组，表示各顶点自成一个连通分量
	for (int i = 0; i < G.vexnum; i++)
	{
		Vexset[i] = i;
	}

	//依次查看数组Edge中的边
	for (int j = 0; j < G.arcnum; j++)
	{
		//v1为边的始点Head的下标
		int v1 = LocateVex(G, Edge[j].Head);
		//v2为边的终点Tail的下标 
		int v2 = LocateVex(G, Edge[j].Tail);
		//v2为边的终点Tail的下标 
		int vs1 = Vexset[v1];
		//获取边Edge[i]的终点所在的连通分量vs2 
		int vs2 = Vexset[v2];
		//边的两个顶点分属不同的连通分量 
		if (vs1 != vs2)
		{
			//边的两个顶点分属不同的连通分量 
			cout << Edge[j].Head << "--->" << Edge[j].Tail << endl;
			//合并vs1和vs2两个分量，即两个集合统一编号 
			for (int k = 0; k < G.vexnum; k++)
			{
				//集合编号为vs2的都改为vs1 
				if (Vexset[k] == vs2)
				{
					Vexset[k] = vs1;
				}
			}
		}
	}

}



int main() {

	AMGraph G;
	//创建无向网的邻接矩阵
	CreateUDN(G);
	//输出无向网的邻接矩阵
	ShowGraph(G);

	
	cout << "************算法6.9　克鲁斯卡尔算法**************" << endl;
	MiniSpanTree_Kruskal(G);

	system("pause");
	return 0;
}