/* 用鄰接矩陣表示的圖的Kruskal算法的源程序*/


#include<stdio.h>
#define MAXVEX 6

typedef char VexType;

typedef float AdjType;

typedef struct {
    int n;                          /* 圖的頂點個數 */
    /*VexType vexs[MAXVEX];         頂點信息 */
    AdjType arcs[MAXVEX][MAXVEX];   /* 邊信息 */
} GraphMatrix;

typedef struct{
    int start_vex, stop_vex;        /* 邊的起點和終點 */
    AdjType weight;                 /* 邊的權 */
} Edge;

Edge mst[5];

#define MAX 1e+8

void prim(GraphMatrix * pgraph, Edge mst[]) {
    int i, j, min, vx, vy; 
    float weight, minweight; Edge edge;

    for (i = 0; i < pgraph->n-1; i++) {
        mst[i].start_vex = 0;
        mst[i].stop_vex = i+1;
        mst[i].weight = pgraph->arcs[0][i+1];
    }

    for (i = 0; i < pgraph->n-1; i++) {               /* 共n-1條邊 */
        minweight = MAX;  min = i;
        for (j = i; j < pgraph->n-1; j++)/* 從所有邊(vx,vy)(vx∈U,vy∈V-U)中選出最短的邊 */
            if(mst[j].weight < minweight) {
                minweight = mst[j].weight; 
                min = j;
            }

        /* mst[min]是最短的邊(vx,vy)(vx∈U, vy∈V-U)，將mst[min]加入最小生成樹 */
        edge = mst[min];  
        mst[min] = mst[i];   
        mst[i] = edge;
        vx = mst[i].stop_vex;            /* vx為剛加入最小生成樹的頂點的下標 */

        for(j = i+1; j < pgraph->n-1; j++) { /* 調整mst[i+1]到mst[n-1] */
            vy=mst[j].stop_vex; weight = pgraph->arcs[vx][vy];
            if (weight < mst[j].weight) {
                mst[j].weight = weight;  
                mst[j].start_vex = vx;
            }
        }
    }
}

GraphMatrix graph = {
    6,
    {{0,10,MAX,MAX,19,21},
     {10,0,5,6,MAX,11},
     {MAX,5,0,6,MAX,MAX},
     {MAX,6,6,0,18,14},
     {19,MAX,MAX,18,0,33},
     {21,11,MAX,14,33,0}
    }
};

int main(){
    int i;
    prim(&graph,mst);
    for (i = 0; i < graph.n-1; i++)
        printf("(%d %d %.0f)\n", mst[i].start_vex,
                mst[i].stop_vex, mst[i].weight);
    return 0;
}