#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#define max_sum 30
#define INFINITY 65535
using namespace std;
typedef struct Arcnode{
int adjvex;
struct Arcnode *nextarc;
}Arcnode;
typedef struct Vexnode{
char data;
struct Arcnode *firstarc;
}Vnode,AdjList[max_sum];
typedef struct Graph{
AdjList vexlist;
int vex_sum;
int arc_sum;
int arc_matrix[max_sum][max_sum];
}Graph;
int visit[max_sum];
void MiniSpanTree(Graph &g){
int min;
int adjvex[max_sum];
int lowest[max_sum];
lowest[1] = 0;
adjvex[1] = 1;
int k = 1;
for(int i = 1;i <= g.vex_sum;i++)
{
lowest[i] = g.arc_matrix[1][i];
adjvex[i] = 1;
}
for(int i = 1;i < g.vex_sum;i++)
{
min = INFINITY;
int j = 1;
while(j <= g.vex_sum)
{
if(lowest[j] < min && lowest[j] != 0)
{
min = lowest[j];
k = j;
}
j++;
}
printf("%d--->%d\n" , adjvex[k],k);
lowest[k] = 0;
for(int j = 1;j <= g.vex_sum;j++){
if(g.arc_matrix[k][j] <= lowest[j] && lowest[j] != 0){
lowest[j] = g.arc_matrix[k][j];
adjvex[j] = k;
}
}
}
}
void creat_graph(Graph &g){
cout<<"输入顶点和边的个数："<<endl;
cin>>g.vex_sum>>g.arc_sum;
for(int i = 1;i <= g.vex_sum;i++)
for(int j = 1;j <= g.vex_sum;j++)
g.arc_matrix[i][j] = -1;
for(int i = 1;i <= g.arc_sum;i++)
{
cout<<"输入起点和终点："<<endl;
int s,e;
cin>>s>>e;
Arcnode *p = new Arcnode;
p->adjvex = e;
p->nextarc = g.vexlist[s].firstarc;
g.vexlist[s].firstarc = p;
cout<<"输入 "<<s<<" ----> "<<e<<" 的路径权值"<<endl;
cin>>g.arc_matrix[s][e];
g.arc_matrix[e][s] = g.arc_matrix[s][e];
}
for(int i = 1;i <= g.vex_sum;i++)
for(int j = 1;j <= g.vex_sum;j++)
if(g.arc_matrix[i][j] == -1)
{
g.arc_matrix[i][j] = INFINITY;
if(i == j)g.arc_matrix[i][j] = 0;
}
}
main(){
Graph g,r;
creat_graph(g);
MiniSpanTree(g);
}
