C语言邻接矩阵构建带权图并写出相应的普里姆算法和克鲁斯卡尔算法

好的，下面是关于C语言邻接矩阵构建带权图以及实现相应的普里姆算法和克鲁斯卡尔算法的一些代码示例：

1. 邻接矩阵构建带权图

#include <stdio.h>
#define MAX 100
#define INF 0x3f3f3f3f // 用来表示无穷大

int graph[MAX][MAX]; // 存储图的邻接矩阵
int n, m; // n表示节点数，m表示边数

int main() {
    scanf("%d%d", &n, &m);
    // 初始化邻接矩阵，将所有边的权值设置为无穷大
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            graph[i][j] = INF;
        }
    }
    // 读入每条边的信息，并将对应的权值存入邻接矩阵中
    for(int i = 1; i <= m; i++) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        graph[u][v] = graph[v][u] = w;
    }
    return 0;
}

2. 实现普里姆算法

#define MAX 100
#define INF 0x3f3f3f3f

int graph[MAX][MAX];
int n; // 节点数

int prim() {
    int dis[MAX], vis[MAX];
    int ans = 0;
    // 初始化dis数组，表示每个节点到已选集合的最短距离
    for(int i = 1; i <= n; i++) {
        dis[i] = graph[1][i];
        vis[i] = 0; // vis数组表示每个节点是否已加入已选集合
    }
    vis[1] = 1; // 从1号节点开始构建最小生成树
    // 每次选取距离已选集合最近的节点
    for(int i = 1; i < n; i++) {
        int minn = INF, pos = -1;
        for(int j = 1; j <= n; j++) {
            if(!vis[j] && dis[j] < minn) {
                minn = dis[j];
                pos = j;
            }
        }
        if(pos == -1) return -1; // 如果无法构建最小生成树，返回-1
        ans += minn;
        vis[pos] = 1;
        // 更新dis数组
        for(int j = 1; j <= n; j++) {
            if(!vis[j] && dis[j] > graph[pos][j]) {
                dis[j] = graph[pos][j];
            }
        }
    }
    return ans;
}

3. 实现克鲁斯卡尔算法

#define MAX 100
#define INF 0x3f3f3f3f

struct Edge {
    int u, v, w;
} edges[MAX * MAX]; // 存储所有边的信息

int fa[MAX]; // 并查集数组
int n, m; // n表示节点数，m表示边数

int find(int x) { // 并查集查找
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}

int kruskal() {
    int ans = 0;
    // 初始化并查集数组
    for(int i = 1; i <= n; i++) {
        fa[i] = i;
    }
    // 将所有边按照权值从小到大排序
    sort(edges + 1, edges + 1 + m, [](const Edge& a, const Edge& b) {
        return a.w < b.w;
    });
    // 依次加入边
    for(int i = 1; i <= m; i++) {
        int u = edges[i].u, v = edges[i].v, w = edges[i].w;
        int x = find(u), y = find(v);
        if(x != y) { // 如果两个节点不在同一个连通块中，就将它们合并
            fa[x] = y;
            ans += w;
        }
    }
    // 如果最终只有一个连通块，说明构建成功
    for(int i = 1; i <= n; i++) {
        if(find(i) != find(1)) {
            return -1; // 如果无法构建最小生成树，返回-1
        }
    }
    return ans;
}

以上就是关于C语言邻接矩阵构建带权图以及实现相应的普里姆算法和克鲁斯卡尔算法的一些代码示例，希望对你有所帮助。