数据结构实验代码克鲁斯卡尔算法.rar

#include<iostream> #include<stdlib.h> #define maxvex 20 using namespace std; class EdgeNode//边 { public: int adjvex;//下标 int weight;//权值 int v1, v2; EdgeNode *next; }; class Node: public EdgeNode//点集合 { public: int data;//点名称 int find;//查找点 EdgeNode *first;//边表头指针 }; class Graph: public EdgeNode, Node { private: int numvex;//点数量 int numedge;//边数量 Node node[maxvex]; public: Graph(); void print(); void Kruskal(); }; Graph::Graph() { cout<<"请输入点数量："; cin>>numvex; cout<<"请输入边数量："; cin>>numedge; EdgeNode *e = NULL; EdgeNode *q = NULL; cout<<"请输入顶点信息："<<endl; for(int i=0;i<numvex;i++) { cin>>node[i].data; node[i].find = i; node[i].next = NULL; } for(int i=0;i<numvex;i++) { node[i].first = NULL; } for(int i=0;i<numedge;i++) { int m, n, w; cout<<"请输入(vi, vj)的顶点下标："<<endl; cin>>m>>n; cout<<"请输入权重："; cin>>w; e = (EdgeNode*) malloc (sizeof(EdgeNode)); e->adjvex = n; e->weight = w; e->next = NULL; if(node[m].first==NULL) q = node[m].first = e; else q = q->next = e; q->next = NULL; } } void Graph::print() { EdgeNode *p; for(int i=0;i<numvex;i++) { if(node[i].first) { cout<<"顶点"<<i<<":"; for(p = node[i].first;p;p=p->next) cout<<p->adjvex<<"("<<p->weight<<") "; if(p==NULL) cout<<endl; } } } void Graph::Kruskal() { EdgeNode *edge[numedge]; EdgeNode *p; for(int i=0, j=0;i<numedge;) { if(node[j].first==NULL) j++; else { p = node[j].first; edge[i] = p; edge[i]->v1 = j; edge[i]->v2 = p->adjvex; p = p->next; i++; while(p) { edge[i] = p; edge[i]->v1 = j; edge[i]->v2 = p->adjvex; p = p->next; i++; } j++; } } int min; EdgeNode *edge_temp; for(int i=0;i<numedge;i++) { min = edge[i]->weight; for(int j=i;j<numedge;j++) { if(min>edge[j]->weight) { edge_temp = edge[j]; edge[j] = edge[i]; edge[i] = edge_temp; min = edge[i]->weight; } } } cout<<endl; for(int i=0;i<numedge;i++) { cout<<edge[i]->v1<<" "<<edge[i]->v2<<endl; } for(int i=0;i<numedge;i++) { if(node[edge[i]->v1].find!=node[edge[i]->v2].find) { cout<<edge[i]->v1<<" "<<edge[i]->v2<<endl; int temp1 = node[edge[i]->v1].find>node[edge[i]->v2].find?node[edge[i]->v1].find:node[edge[i]->v2].find; int temp2 = node[edge[i]->v1].find<node[edge[i]->v2].find?node[edge[i]->v1].find:node[edge[i]->v2].find; for(int j=0;j<numvex;j++) if(node[j].find==temp1) node[j].find = temp2; } } } int main() { Graph g; g.Kruskal(); g.print(); }