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