kruskal.cpp

数据结构经典算法的C语言实现 计算机专业数据结构课程实验

#include<iostream.h>

#define MAX 500

int dfn[100];     //顶点的先深编号
int bfn[100];     //顶点的先广编号
int count;
enum Boolen{TRUE, FALSE};
Boolen visited[100];

struct EdgeNode {
	int adjvex;
	int cost;
	EdgeNode *next;
};  //边表结点
struct VertexNode {
	char vertex;
	EdgeNode *firstedge;
};  //顶点结点
struct AdjGraph {
	VertexNode vexlist[100];
	int n, e;
};  //图结点
AdjGraph adg;
struct MgGraph {
	char vexlist[100];
	int edge[100][100];
	int n, e;
};  //图的邻接矩阵
MgGraph mg;

//创建邻接矩阵
void CREATMG(void) {
	int i, j, k, m;
	
	cout<<"请输入图的顶点数（不超过"<<MAX<<"个）：";	
	cin>>mg.n;
	cout<<"请输入图的边数：";
	cin>>mg.e;

	cout<<endl<<"程序已自动将图的"<<mg.n<<"个顶点编号，从0到"<<mg.n-1<<"。"<<endl;
	for(i = 0;i < mg.n;i++)
		mg.vexlist[i] = i;
	for(i = 0;i < mg.n;i++)
		for(j = 0;j < mg.n;j++)
			mg.edge[i][j] = MAX;
		
	cout<<"按照顶点编号输入各边。"<<endl<<endl;
	for(k = 0;k < mg.e;k++) {
		cout<<"请输入第"<<k+1<<"条边的起点编号：";
		cin>>i;
		cout<<"请输入第"<<k+1<<"条边的终点编号：";
		cin>>j;
		cout<<"请输入第"<<k+1<<"条边的权值：";
		cin>>m;
		mg.edge[i][j] = m;
		mg.edge[j][i] = m;
	}
}
//先深遍历
void DFS1(MgGraph g, int i) {
	int j;
	visited[i] = TRUE;
	for(j = 0;j < g.n;j++)
		if(g.edge[i][j] < MAX && visited[j] == FALSE)
			DFS1(g, j);
}
//求解函数
void KRUSKAL1(void) {
	int i, j, k, temp, ncomp;
	int a[100 * 100][3];
	MgGraph t;
	
	t.n = mg.n;
	t.e = 0;
	for(i = 0;i < mg.n;i++)
		t.vexlist[i] = mg.vexlist[i];
	for(i = 0;i < mg.n;i++)
		for(j = 0;j < mg.n;j++)
			t.edge[i][j] = MAX;

	ncomp = mg.n;
	k = 0;
	for(i = 0;i < mg.n;i++)
		for(j = i + 1;j < mg.n;j++) {
			a[k][0] = mg.edge[i][j];
			a[k][1] = i;
			a[k][2] = j;
			k++;
		}
	a[k][0] = MAX;
	for(i = 0;i < k;i++)
		for(j = i + 1;j < k;j++) {
			if(a[i][0] > a[j][0]) {
				temp = a[i][0];
				a[i][0] = a[j][0];
				a[j][0] = temp;
				temp = a[i][1];
				a[i][1] = a[j][1];
				a[j][1] = temp;
				temp = a[i][2];
				a[i][2] = a[j][2];
				a[j][2] = temp;
			}
		}
	i = -1;
	while(ncomp > 1) {
		i++;
		for(j = 0;j < t.n;j++)
			visited[j] = FALSE;
		DFS1(t, a[i][1]);
		if(visited[a[i][2]] == FALSE) {
			t.e++;
			t.edge[a[i][1]][a[i][2]] = a[i][0];
			t.edge[a[i][2]][a[i][1]] = a[i][0];
			cout<<"("<<a[i][1]<<","<<a[i][2]<<")    ";
			ncomp--;
		}
	}
}

//创建邻接表
void CREATADJ(void) {
	int i, tail, head;
	int weight;
	EdgeNode *p;

	cout<<"请输入图的顶点数（不超过"<<MAX<<"个）：";
	cin>>adg.n;
	cout<<"请输入图的边数：";
	cin>>adg.e;

	cout<<endl<<"程序已自动将图的"<<adg.n<<"个顶点编号，从0到"<<adg.n-1<<"。"<<endl;
	for(i = 0;i < adg.n;i++) {
		adg.vexlist[i].vertex = i;
		adg.vexlist[i].firstedge = NULL;
	}
	cout<<"按照顶点编号输入各边。"<<endl<<endl;
	for(i = 0;i < adg.e;i++) {
		cout<<"请输入第"<<i+1<<"条边的起点编号：";
		cin>>head;
		cout<<"请输入第"<<i+1<<"条边的终点编号：";
		cin>>tail;
		cout<<"请输入第"<<i+1<<"条边的权值：";
		cin>>weight;
		p = new EdgeNode;
		p->adjvex = tail;
		p->cost = weight;
		p->next = adg.vexlist[head].firstedge;
		adg.vexlist[head].firstedge = p;
		p = new EdgeNode;
		p->adjvex = head;
		p->cost = weight;
		p->next = adg.vexlist[tail].firstedge;
		adg.vexlist[tail].firstedge = p;
	}
}
//先深遍历
void DFS2(AdjGraph g, int i) {
	EdgeNode *p;

	visited[i] = TRUE;
	p = g.vexlist[i].firstedge;
	while(p) {
		if(visited[i] == FALSE)
			DFS2(g, p->adjvex);
		p = p->next;
	}
}
//求解函数
void KRUSKAL2(AdjGraph g) {
	int i, j, k, temp, ncomp;
	int a[100 * 100][3];
	AdjGraph t;
	EdgeNode *p;

	t.n = g.n;
	t.e = 0;
	for(i = 0;i < g.n;i++) {
		t.vexlist[i].vertex = g.vexlist[i].vertex;
		t.vexlist[i].firstedge = NULL;
	}

	ncomp = g.n;
	k = 0;
	for(i = 0;i < g.n;i++) {
		p = g.vexlist[i].firstedge;
		while(p) {
			if(p->adjvex > i) {
				a[k][0] = p->cost;
				a[k][1] = i;
				a[k][2] = p->adjvex;
				k++;
			}
			p = p->next;
		}
	}
	a[k][0] = MAX;
	for(i = 0;i < k;i++)
		for(j = i + 1;j < k;j++)
			if(a[i][0] > a[j][0]) {
				temp = a[i][0];
				a[i][0] = a[j][0];
				a[j][0] = temp;
				temp = a[i][1];
				a[i][1] = a[j][1];
				a[j][1] = temp;
				temp = a[i][2];
				a[i][2] = a[j][2];
				a[j][2] = temp;
			}
	i = -1;
	while(ncomp > 1) {
		i++;
		for(j = 0;j < t.n;j++)
			visited[j] = FALSE;
		DFS2(t,a[i][1]);
		if(visited[a[i][2]] == FALSE) {
			t.e++;
			p = new EdgeNode;
			p->cost = a[i][0];
			p->adjvex = a[i][1];
			p->next = t.vexlist[a[i][2]].firstedge;
			t.vexlist[a[i][2]].firstedge = p;
			p = new EdgeNode;
			p->cost = a[i][0];
			p->adjvex = a[i][2];
			p->next = t.vexlist[a[i][1]].firstedge;
			t.vexlist[a[i][1]].firstedge = p;
			cout<<"("<<a[i][1]<<","<<a[i][2]<<")    ";
			ncomp--;
		}
	}
	cout<<endl;
}

void main() {
label:
	char i;
	char yn;
	cout<<"请选择图的表示方式：1、邻接矩阵     2、邻接表     ";
	cin>>i;
	if(i == '1') {
		CREATMG();
		cout<<endl<<"最小生成树选择的边如下："<<endl;
		KRUSKAL1();
		cout<<endl;
	}
	else if(i == '2') {
		CREATADJ();
		cout<<endl<<"最小生成树选择的边如下："<<endl;
		KRUSKAL2(adg);
	}
	else {
		cout<<"选择错误，请重新选择！"<<endl;
		goto label;
	}
	cout<<"是否继续使用本程序？Y继续使用，N退出程序：";
	cin>>yn;
	if(yn == 'y' || yn == 'Y')
		goto label;
}