Prime and kruskal

#include <stdio.h>
#define MaxSize 100
#define INF 32767    /*INF表示∞*/
#define MAXV 100    /*最大顶点个数*/
typedef int InfoType;
typedef struct {
    int no;                        /*顶点编号*/
    InfoType info;                /*顶点其他信息*/
} VertexType;                    /*顶点类型*/
typedef struct {                /*图的定义*/
    int edges[MAXV][MAXV];         /*邻接矩阵*/
    int n, e;                      /*顶点数，弧数*/
    VertexType vexs[MAXV];        /*存放顶点信息*/
} MGraph;                        /*图的邻接矩阵类型*/
typedef struct {
    int u;            /*边的起始顶点*/
    int v;            /*边的终止顶点*/
    int w;            /*边的权值*/
} Edge;
void InsertSort(Edge E[], int n); /*对E[0..n-1]按递增有序进行直接插入排序*/
void Kruskal(MGraph g);
void Prim(MGraph g, int v);
#include <stdio.h>
#include <stdlib.h>
//prim
void Prim(MGraph g, int v) {
    int lowcost[MAXV];            /*顶点i是否在U中*/
    int min;
    int closest[MAXV], i, j, k;

    for(i = 0; i < g.n; i++) {       /*给lowcost[]和closest[]置初值*/
        lowcost[i] = g.edges[v][i];
        closest[i] = v;
    }

    for(i = 1; i < g.n; i++) {       /*找出n-1个顶点*/
        /*在(V-U)中找出离U最近的顶点k，用k记录最近顶点的编号*/
        min = INF;

        /********** Begin **********/
        for(j = 0; j < g.n; j++) {
            if(lowcost[j] != 0 && lowcost[j] < min) {
                min = lowcost[j];
                k = j;
            }
        }

        /********** End **********/
        printf("(%d,%d):%d\n", closest[k], k, min);
        lowcost[k] = 0;           /*标记k已经加入U*/

        /*修改数组lowcost和closest*/
        /********** Begin **********/
        for(j = 0; j < g.n; j++) {
            if(g.edges[k][j] != 0 && g.edges[k][j] < lowcost[j]) {
                lowcost[j] = g.edges[k][j];
                closest[j] = k;
            }
        }

        /********** End **********/
    }
}
/*实现克鲁斯卡尔算法的难点在于“如何判断一个新边是否会和已选择的边构成环路”，
这里教大家一种判断的方法：初始状态下，为连通网中的各个顶点配置不同的标记。
对于一个新边，如果它两端顶点的标记不同，就不会构成环路，可以组成最小生成树。
一旦新边被选择，需要将它的两个顶点以及和它直接相连的所有已选边两端的顶点改为相同的标记；
反之，如果新边两端顶点的标记相同，就表示会构成环路。*/
//krusal
void InsertSort(Edge E[], int n) { /*对E[0..n-1]按递增有序进行直接插入排序*/
    int i, j;
    Edge temp;

    for(i = 1; i < n; i++) {
        temp = E[i];
        j = i - 1;            /*从右向左在有序区E[0..i-1]中找E[i]的插入位置*/

        while(j >= 0 && temp.w < E[j].w) {
            E[j + 1] = E[j]; /*将关键字大于E[i].w的记录后移*/
            j--;
        }

        E[j + 1] = temp;    /*在j+1处插入E[i] */
    }
}
void Kruskal(MGraph g) {
    /********** Begin **********/
    int assists[MaxSize];
    int k = 0;

    for(int i = 0; i < g.n; i++) {
        assists[i] = i;
    }

    Edge e[MaxSize];

    for(int i = 0; i < g.n; i++) {
        for(int j = 0; j < g.n; j++) {
            if(g.edges[i][j] != 0 && g.edges[i][j] != INF) {
                e[k].u = i;
                e[k].v = j;
                e[k].w = g.edges[i][j];
                k++;
            }
        }
    }

    InsertSort(e, g.e);
    k = 1; //生成树的第几条边
    int u1, v1, n1, n2, j = 0; //第j条边

    while(k < g.n) {
        u1 = e[j].u;
        v1 = e[j].v;
        n1 = assists[u1];
        n2 = assists[v1];

        if(n1 != n2) {
            printf("(%d,%d):%d\n", u1, v1, e[j].w);
            k++;

            for(int i = 0; i < g.n; i++) {
                if(assists[i] == n2) {
                    assists[i] = n1;
                }
            }
        }

        j++;//扫描下一条边
    }

    /********** End **********/
}
int main() {
    int i, j;
    MGraph g;
    int n, e;
    scanf("%d %d", &n, &e);
    g.n = n;
    g.e = e;
    int a[MAXV][MAXV];

    for(i = 0; i < n; i++) {
        for(j = 0; j < n; j++) {
            scanf("%d", &a[i][j]);
        }
    }

    for(i = 0; i < g.n; i++)   /*建立图9.13(a)所示的图的邻接矩阵*/
        for(j = 0; j < g.n; j++)
            g.edges[i][j] = a[i][j];

    printf("Krusal:\n");
    Kruskal(g);
    printf("Prim:\n");
    Prim(g, 0);
    printf("\n");
    return 0;
}