#include
using namespace std;
const int Maxsize=100;
struct RS {
int lowcost;
int adjvex;
};
typedef struct {
char Vertex[Maxsize];
int vertexNum;
int arcNum;
int arc[Maxsize][Maxsize];
} MGraph;
int MinEdge(RS shortEdge[],int n) {
int i=0;
int min=3000;
for(int j=0; j<n; j++) {
if(shortEdge[j].lowcost<min&&shortEdge[i].lowcost!=0){
min=shortEdge[j].lowcost;
i=j;
}
}
return i;
}
void Prime(MGraph G) {
RS shortEdge[Maxsize];
int k;
for(int i=0; i<G.vertexNum; i++) {
shortEdge[i].lowcost=G.arc[0][i];
shortEdge[i].adjvex=0;
}
shortEdge[0].lowcost=0;
for(int i=1; i<G.vertexNum; i++) {
k=MinEdge(shortEdge,G.vertexNum);
cout<<k<<endl;
cout<<"("<<shortEdge[k].adjvex<<")"<<shortEdge[k].lowcost;
shortEdge[k].lowcost=0;
for(int j=1; j<G.vertexNum; j++) {
if(G.arc[k][j]<shortEdge[j].lowcost) {
shortEdge[j].lowcost=G.arc[k][j];
shortEdge[j].adjvex=k;
}
}
}
}
int main() {
MGraph G;
G.vertexNum=6;
G.arcNum=9;
//G.arc[Maxsize][Maxsize]={0};
char b[6]= {'a','b','c','d','e','f'};
for(int i=0; i<6; i++)
G.Vertex[i]=b[i];
int a[6][6]= { 0,34,46,3000,3000,19, 34,0,3000,3000,12,3000,46,3000,0,17,3000,25,3000,3000,17,0,38,25,
3000,12,3000,38,0,26,
19,3000,25,26,25,0
};
for(int i=0; i<6; i++) {
for(int j=0; j<6; j++) {
G.arc[i][j]=a[i][j];
}
}
Prime(G);
return 0;
}
