最小生成树.cpp

最小生产树

#define MAX_VERTEX_NUM 100
#define OK 1
#define ERROR -1
#define INFINITY 10000
#include <time.h>
#include <iostream>
using namespace std;
typedef int Status;
typedef struct Adjlist {
	int set;
	char vex;
}Adjlist;
typedef struct ArcNode {
	bool tag;
	char head;
	char tail;
	int weight;
}ArcNode;
typedef struct UdGraph{
	int vexnum, edgenum;
	Adjlist vexinform[MAX_VERTEX_NUM];
	ArcNode Arc[MAX_VERTEX_NUM];
}UdGraph;

UdGraph Graph;

int locate(char c) {
	for(int k = 0; k < Graph.vexnum; k++) 
		if(c == Graph.vexinform[k].vex) return k;
	return ERROR;
}
Status Init(UdGraph &Graph) {
	srand((unsigned)time(NULL));
	cout << "请输入顶点数：" << endl;
	cin >> Graph.vexnum;
	cout << "请输入各顶点：" << endl;
	for(int i = 0; i < Graph.vexnum; i++) {
		Graph.vexinform[i].set = i;
		cin >> Graph.vexinform[i].vex;
	}
	cout << "请输入边数：" << endl;
	cin >> Graph.edgenum;
	cout << "请输入各边：" << endl;
	for(i = 0; i < Graph.edgenum; i++) {
		Graph.Arc[i].tag = false;
		cin >> Graph.Arc[i].head >> Graph.Arc[i].tail;
		Graph.Arc[i].weight = rand() % 100 + 1;
		}
	cout << "各边及其权值依次是：" << endl;
	for(i = 0; i < Graph.edgenum; i++) {
		cout << Graph.Arc[i].head << "--" << Graph.Arc[i].tail << "  weight = " << Graph.Arc[i].weight << endl;
	}
return OK;
}
Status Kruskal(UdGraph &Graph) {
	char ch, ct;
	int h, t, minarc;
	cout << "最小生成树各边及其权值依次为：" << endl;
	for(int i = 0; i < Graph.edgenum; i ++) {
		for(int k = 0, min = INFINITY; k < Graph.edgenum; k ++) {
			if(Graph.Arc[k].tag == false && Graph.Arc[k].weight < min) {
				ch = Graph.Arc[k].head;
				ct = Graph.Arc[k].tail;
				min = Graph.Arc[k].weight;
				minarc = k;
			}
		}
		Graph.Arc[minarc].tag = true;
		h = locate(ch);
		t = locate(ct);
		if(Graph.vexinform[h].set != Graph.vexinform[t].set) {
			cout << Graph.vexinform[h].vex << "--" << Graph.vexinform[t].vex << "  " << min << endl;
			for(int j = 0; j < Graph.vexnum; j++) 
				if(Graph.vexinform[j].set == Graph.vexinform[t].set) Graph.vexinform[j].set = Graph.vexinform[h].set;
		}
	}
	return OK;
}
int main() {
	Init(Graph);
	Kruskal(Graph);
	return 0;
}