least_tree.rar_C Builder_C++ builder tree_tree

#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; }