Prim算法

#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);
bool IsComplete(bool *mstSet, int number);
int MinWeight(MGraph *m, bool* mstSet, int number);

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);

    // Initialize MST
    for (int i = 0; i < number; i++) {
        *(mstSet + i) = false;
    }
    *(mstSet + start) = true;
    while (!IsComplete(mstSet, number)) {
        int end = MinWeight(m, mstSet, number);
        *(mstSet + end) = true;
    }
}
bool IsComplete(bool *mstSet, int number) {
    int i = 0;
    for (int i = 0; i < number; i++) {
        if (!*(mstSet + i)) {
            return false;
        }
    }
    return true;
}
int MinWeight(MGraph *m, bool* mstSet, int number) {
    int min = Infiniate;
    int start, end;
    for (int k = 0; k < number; k++) {
        if (*(mstSet + k)) {
            for (int i = 0; i < number; i++) {
                if ((m->Edge[k][i] > 0) && (m->Edge[k][i] < min) && !*(mstSet + i)) {
                    min = m->Edge[k][i];
                    start = k;
                    end = i;
                }
            }
        }
    }
    printf("%d --> %d   %d\n", start, end, min);
    return end;
}
/*
 时间复杂度O(n^3), Prim算法的原本时间复杂度应该是O(n^2)
输入:
8
0
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
结果:
4 --> 1   3
1 --> 2   5
2 --> 0   1
2 --> 5   4
5 --> 3   2
 */