C语言构建带权的邻接矩阵并实现普里姆算法和克鲁斯卡尔算法在邻接矩阵的应用

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

1. 构建带权的邻接矩阵

#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语言构建带权的邻接矩阵并实现普里姆算法和克鲁斯卡尔算法在邻接矩阵的应用的一些代码示例和说明，希望对你有所帮助。邻接矩阵是图的一种表示方式，它将图中的节点和边都用矩阵表示出来，并将节点和矩阵的行列一一对应。在实现算法时，我们可以通过访问矩阵中的元素来获取节点之间的关系和边的权值，从而完成图的遍历和最小生成树的构建。