最小生成树（普里姆算法）

最小生成树：含有图中全部顶点，但只有足以构成一棵树的n - 1条边的连通子图，并且该连通子图所有边上的权值之和最小。

普里姆算法：从某一顶点n开始，把与顶点n相连的顶点的权值都加入lowcost数组；之后进行循环，每次从lowcost数组中选出权值最小的边和顶点k进行打印，将lowcost[n]设置为0（表示n顶点已加入生成树），并将与k相连顶点的权值加入lowcost数组，用adjvex数组记录与顶点k相连的顶点，如此循环。

实现代码如下：

// 最小生成树（普里姆算法）
#include <stdio.h>

#define MAXVEX 100 // 最大顶点数
#define INFINITY 65535 // 无穷

typedef int EdgeType; // 边上的权值类型

// 邻接矩阵结构
typedef struct {
    EdgeType arc[MAXVEX][MAXVEX]; // 边表
    int numNodes, numEdges; // 图中当前的顶点数，边数
}MGraph;


/**
 * 生成邻接矩阵
 * @param G 邻接矩阵
 */
void CreateMGraph(MGraph *G) {
    int i, j; // 用于遍历元素

    G->numEdges = 15; // 设置有15条边
    G->numNodes = 9; // 设置有9个顶点

    // 初始化图的边
    for (i = 0; i < G->numNodes; i++) {
        for (j = 0; j < G->numNodes; j++) {
            if (i == j) { // 对角线边的值设置为0
                G->arc[i][j] = 0;
            } else { // 其他位置的边设置为无穷
                G->arc[i][j] = G->arc[j][i] = INFINITY;
            }
        }
    }

    // 设置特定边的权
    G->arc[0][1] = 10;
    G->arc[0][5] = 11;

    G->arc[1][2] = 18;
    G->arc[1][8] = 12;
    G->arc[1][6] = 16;

    G->arc[2][3] = 22;
    G->arc[2][8] = 21;

    G->arc[3][4] = 20;
    G->arc[3][7] = 16;
    G->arc[3][6] = 24;
    G->arc[3][8] = 21;

    G->arc[4][5] = 26;
    G->arc[4][7] = 7;

    G->arc[5][6] = 17;

    G->arc[6][7] = 19;

    // 设置对称边的权
    for (i = 0; i < G->numNodes; i++) {
        for (j = i; j < G->numNodes; j++) {
            G->arc[j][i] = G->arc[i][j];
        }
    }
}

/**
 * 打印下标
 */
void PrintIndex() {
    printf(" index: ");
    for (int i = 0; i < 9; ++i) {
        printf("\t%d ", i);
    }
    printf("\n");
}

/**
 * 打印lowcost数组
 * @param lowcost 存备用最小权值的数组
 */
void PrintLowcost(int lowcost[]) {
    printf("lowcost: ");
    for (int i = 0; i < 9; ++i) {
        printf("\t%d ", lowcost[i]);
    }
    printf("\n");
}

/**
 * 打印adjvex数组
 * @param adjvex 存边对应顶点的数组
 */
void PrintAdjvex(int adjvex[]) {
    printf("adjvex: ");
    for (int i = 0; i < 9; ++i) {
        printf("\t%d ", adjvex[i]);
    }
    printf("\n");
}

/**
 * Prim算法生成最小生成树
 * @param G 最小生成树
 */
void MiniSpanTree_Prim(MGraph G) {
    int min, k, i, j; // min存储最小值，k用来存储最小值下标，i、j用于遍历元素
    int adjvex[MAXVEX]; // 存储顶点下标
    int lowcost[MAXVEX]; // 保存顶点间边的权值

    // 初始化第一个权值为0，即将v0加入生成树，lowcost的值为0，表示改下标的顶点已加入生成树
    lowcost[0] = 0;
    adjvex[0] = 0; // 初始化第一个顶点下标为0

    // 对下标为0以外的顶点进行遍历
    for (i = 1; i < G.numNodes; i++) {
        lowcost[i] = G.arc[0][i]; // 将与v0顶点有边的权值存入数组
        adjvex[i] = 0; // 顶点初始化都为v0的下标
    }

    // 对下标为0以外的顶点进行遍历
    for (i = 1; i < G.numNodes; i++) {
        min = INFINITY; // 初始化本次循环的边最小值为无穷

        j = 1; // 用来遍历v0以外的顶点
        k = 0; // 记录最小边的下标

        // 循环全部顶点
        while (j < G.numNodes) {
            // 权值不为0（权值为0表示已加入生成树）并且小于min
            if (lowcost[j] != 0 && lowcost[j] < min) {
                min = lowcost[j]; // 让当前权值成为最小值
                k = j; // 使用k记录当前最小值的下标
            }
            j++; // j向后移动
        }

        PrintIndex(); // 打印下标
        PrintAdjvex(adjvex); // 打印adjvex数组
        PrintLowcost(lowcost); // 打印lowcost数组

        printf("最小权为：%d，边为：(%d, %d)\n\n", min, adjvex[k], k); // 打印与顶点相连的边中权值最小的边
        lowcost[k] = 0; // 设置当前顶点的权值为0，表示该顶点已完成任务

        // 对下标为0以外的顶点进行遍历
        for (j = 1; j < G.numNodes; j++) {
            // 对本次有最小权值的顶点k，把与k相连的边加入数组中
            // 值不为0（权值为0表示已加入生成树）并且小于对应列的lowcost
            if (lowcost[j] != 0 && G.arc[k][j] < lowcost[j]) {
                lowcost[j] = G.arc[k][j]; // 将较小的权值存入lowcost的相应位置
                adjvex[j] = k; // 因为与顶点k相连，将下标为k的顶点存入adjvex
            }
        }

    }
}

int main() {
    MGraph G; // 邻接矩阵
    CreateMGraph(&G); // 创建邻接矩阵
    MiniSpanTree_Prim(G); // Prim算法生成最小生成树

    return 0;
}

运行结果