C语言创建图的邻接矩阵并用普里姆算法求最小生成树

创建图邻接矩阵的步骤如下：

1. 定义一个二维数组来表示图的邻接矩阵，其中第i行第j列的值表示节点i到节点j的边权重。如果两个节点之间没有边，则该位置的值可以设置为无穷大或者一个非常大的值。

2. 初始化邻接矩阵，将所有值都设为无穷大或者一个非常大的值。

3. 遍历所有的边，将相应位置的值设置为边的权重。

下面是一个简单的示例代码：

#include <stdio.h>
#define MAX 100
#define INF 0x7fffffff
 
int G[MAX][MAX];
int n, m;
 
void createGraph() {
    int i, j, u, v, w;
    scanf("%d %d", &n, &m);
    for(i = 1; i <= n; i++) {
        for(j = 1; j <= n; j++) {
            G[i][j] = INF;
        }
    }
    for(i = 1; i <= m; i++) {
        scanf("%d %d %d", &u, &v, &w);
        G[u][v] = G[v][u] = w;
    }
}

接下来，我们使用普里姆算法求最小生成树。普里姆算法是一种贪心算法，它的基本思想是从一个任意节点开始，不断选择与当前生成树相连的最小边，直到所有的节点都被连通为止。具体步骤如下：

1. 选择一个任意节点作为起点，加入生成树中。

2. 遍历与生成树相邻的节点，找到其中权重最小的一条边，将它所连接的节点加入生成树中。

3. 重复步骤2，直到所有的节点都被加入生成树中。

下面是一个简单的示例代码：

void prim() {
    int i, j, k, min, sum = 0;
    int lowcost[MAX], closest[MAX];
    for(i = 2; i <= n; i++) {
        lowcost[i] = G[1][i];
        closest[i] = 1;
    }
    closest[1] = 0;
    for(i = 2; i <= n; i++) {
        min = INF;
        k = 0;
        for(j = 2; j <= n; j++) {
            if(closest[j] != 0 && lowcost[j] < min) {
                min = lowcost[j];
                k = j;
            }
        }
        closest[k] = 0;
        sum += min;
        for(j = 2; j <= n; j++) {
            if(closest[j] != 0 && G[k][j] < lowcost[j]) {
                lowcost[j] = G[k][j];
                closest[j] = k;
            }
        }
    }
    printf("最小生成树的权值之和为：%d\n", sum);
}

在上面的代码中，我们使用两个数组`lowcost`和`closest`来记录生成树中与每个节点相连的最小边和最近的节点。在初始化时，我们将数组`lowcost`和`closest`分别设置为节点1到其他节点的边权重和节点1。接着，我们遍历所有的节点，找到与当前生成树相邻的节点中，权重最小的一条边，并将它所连接的节点加入生成树中。接着，我们更新数组`lowcost`和`closest`中的值，继续遍历下一个节点，直到所有的节点都被加入生成树中。

完整代码如下：

#include <stdio.h>
#define MAX 100
#define INF 0x7fffffff
 
int G[MAX][MAX];
int n, m;
 
void createGraph() {
    int i, j, u, v, w;
    scanf("%d %d", &n, &m);
    for(i = 1; i <= n; i++) {
        for(j = 1; j <= n; j++) {
            G[i][j] = INF;
        }
    }
    for(i = 1; i <= m; i++) {
        scanf("%d %d %d", &u, &v, &w);
        G[u][v] = G[v][u] = w;
    }
}
 
void prim() {
    int i, j, k, min, sum = 0;
    int lowcost[MAX], closest[MAX];
    for(i = 2; i <= n; i++) {
        lowcost[i] = G[1][i];
        closest[i] = 1;
    }
    closest[1] = 0;
    for(i = 2; i <= n; i++) {
        min = INF;
        k = 0;
        for(j = 2; j <= n; j++) {
            if(closest[j] != 0 && lowcost[j] < min) {
                min = lowcost[j];
                k = j;
            }
        }
        closest[k] = 0;
        sum += min;
        for(j = 2; j <= n; j++) {
            if(closest[j] != 0 && G[k][j] < lowcost[j]) {
                lowcost[j] = G[k][j];
                closest[j] = k;
            }
        }
    }
    printf("最小生成树的权值之和为：%d\n", sum);
}
 
int main() {
    createGraph();
    prim();
    return 0;
}

注意，上面的代码中使用了无穷大来表示两个节点之间没有边。在实际使用时，可以根据具体情况选择一个合适的值来表示无穷大。此外，普里姆算法的时间复杂度为O(n^2)，其中n为节点数。当节点数比较大时，可能需要使用更高效的算法来求解最小生成树。