#include <stdio.h>
#include <stdlib.h>

#define MaxVertexNum 100
#define Infiniate 65535
typedef bool VertexType;
typedef int EdgeType;
typedef struct {
    VertexType Vex[MaxVertexNum] = {false};
    EdgeType Edge[MaxVertexNum][MaxVertexNum] = {Infiniate};
    int vexnum, arcnum;
}MGraph;

typedef struct {
    int start;
    int end;
    int weight;
}EdgeArray;

void InitPrim(MGraph *m, int number);
void MSTPrim(MGraph *m, int number, int start);

int main()
{
    MGraph m;
    int number, start;
    printf("Please input the Vertex number: ");
    scanf("%d", &number);
    printf("Please input the starting Vertex");
    scanf("%d", &start);
    InitPrim(&m, number);
    MSTPrim(&m, number, start);
}

void InitPrim(MGraph *m, int number) {
    printf("please input the whole graph, infiniate(65535) is not connected\n");
    int isExist;
    for (int i = 0; i < number; i++) {
        m->Vex[i] = i;
        for (int j = 0; j < number; j++) {
            scanf("%d", &isExist);
            m->Edge[i][j] = isExist;
        }
    }
}
void MSTPrim(MGraph *m, int number, int start) {
    bool *mstSet = (bool *)malloc(sizeof(int)*number); //已访问的MST的顶点
    int *weight = (int *)malloc(sizeof(int)*number);  //权值数组
    int *parent = (int *)malloc(sizeof(int)*number); //  前驱数组

    for (int i = 0; i < number; i++) {
        *(mstSet + i) = false;
        *(weight + i) = m->Edge[start][i];
        *(parent + i) = start;
    }
    *(mstSet + start) = true;

    for (int i = 0; i < number-1; i++) {
        int min = Infiniate;
        int k = 0;
        for (int j = 0; j < number; j++) {
            if (!*(mstSet + j) && *(weight + j) < min) {
                min = *(weight + j);
                k = j;
            }
        }
        printf("%d --> %d  %d\n", *(parent + k), k, min);
        *(mstSet + k) = true;
        for (int i = 0; i < number; i++) {
            if (!*(mstSet + i) && m->Edge[k][i] < *(weight + i)) {
                *(weight + i) = m->Edge[k][i];
                *(parent + i) = k;
            }
        }
    }
}
/*
时间复杂度:O(n^2)
 6
 2
0 6 1 5 65535 65535
6 0 5 65535 3 65535
1 5 0 5 6 4
5 65535 5 0 65535 2
65535 3 6 65535 0 6
65535 65535 4 2 6 0
结果:
 2 --> 0  1
2 --> 5  4
5 --> 3  2
2 --> 1  5
1 --> 4  3
*/