为什么最小生成树邻接矩阵加起来除以2

在最小生成树（Minimum Spanning Tree，MST）问题中，我们需要寻找一棵覆盖所有顶点的树，使得树上所有边的权重之和最小。Prim 和 Kruskal 等算法都可以解决 MST 问题，它们的实现中通常使用邻接矩阵来存储图的信息。

在邻接矩阵中，每个元素表示一条边的权重，如果图中不存在这条边，则该元素的值为无穷大（或者一个很大的数）。当算法计算出最小生成树后，我们将树上所有边的权重相加，得到的结果是最小生成树的权重之和。但是，在邻接矩阵中，每条边的权重通常都被计算了两次，因为它同时出现在起点与终点的邻接矩阵中。所以，我们需要将最小生成树的权重之和除以 2，才能得到最终的结果。

因此，最小生成树邻接矩阵加起来除以 2 的原因是因为每条边的权重在邻接矩阵中被计算了两次，而最小生成树只需要保留其中一条边。

相关问题

c语言最小生成树邻接矩阵求权

以下是使用C语言求解最小生成树邻接矩阵权的示例代码：

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

#define MAX_VERTICES 100
#define INF INT_MAX

int n; // 图中节点数
int adj[MAX_VERTICES][MAX_VERTICES]; // 邻接矩阵
int selected[MAX_VERTICES]; // 已选择的节点
int dist[MAX_VERTICES]; // 节点到最小生成树的距离

// Prim算法求解最小生成树
void prim(int start) {
    int i, j, u, v, min;
    // 初始化
    for (i = 0; i < n; i++) {
        dist[i] = adj[start][i];
        selected[i] = 0;
    }
    selected[start] = 1;
    // 选择n-1个节点
    for (i = 0; i < n - 1; i++) {
        min = INF;
        u = -1;
        // 选择距离最小的节点
        for (j = 0; j < n; j++) {
            if (!selected[j] && dist[j] < min) {
                min = dist[j];
                u = j;
            }
        }
        selected[u] = 1;
        // 更新距离
        for (v = 0; v < n; v++) {
            if (!selected[v] && adj[u][v] < dist[v]) {
                dist[v] = adj[u][v];            }
        }
    }
}

int main() {
    int i, j, start, sum = 0;
    // 读入节点数和邻接矩阵
    scanf("%d", &n);
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            scanf("%d", &adj[i][j]);
        }
    }
    // 选择起始节点
    printf("请输入起始节点：");
    scanf("%d", &start);
    // 求解最小生成树
    prim(start);
    // 计算最小代价
    for (i = 0; i < n; i++) {
        if (dist[i] != INF) {
            sum += dist[i];
        }
    }
    printf("最小生成树的代价为：%d\n", sum);
    return 0;
}

Matlab最小生成树的邻接矩阵

这里提供一个使用Kruskal算法求解最小生成树的邻接矩阵的Matlab代码示例：

% 假设邻接矩阵为A，n为节点数目
% 初始化父节点数组和秩数组
parent = 1:n;
rank = zeros(1, n);

% 定义边结构体
Edge = struct('u', 0, 'v', 0, 'w', 0);

% 构造边集合
edges = [];
for i = 1:n
    for j = i+1:n
        if A(i, j) > 0
            edge.u = i;
            edge.v = j;
            edge.w = A(i, j);
            edges = [edges, edge];
        end
    end
end

% 按权重从小到大排序
edges = sort(edges, @(e1, e2) e1.w - e2.w);

% 定义最小生成树邻接矩阵
MST = zeros(n);

% Kruskal算法求解最小生成树
for i = 1:length(edges)
    u = edges(i).u;
    v = edges(i).v;
    w = edges(i).w;
    
    % 判断是否在同一集合中
    while parent(u) ~= u
        u = parent(u);
    end
    while parent(v) ~= v
        v = parent(v);
    end
    
    if u ~= v
        % 合并两个集合
        if rank(u) < rank(v)
            parent(u) = v;
        elseif rank(v) < rank(u)
            parent(v) = u;
        else
            parent(v) = u;
            rank(u) = rank(u) + 1;
        end
        
        % 添加边到最小生成树
        MST(edges(i).u, edges(i).v) = w;
        MST(edges(i).v, edges(i).u) = w;
    end
end

这段代码将邻接矩阵A转化为边集合，然后使用Kruskal算法求解最小生成树并构造邻接矩阵MST。需要注意的是，这里假设邻接矩阵是对称的（即无向图），因此MST也是对称的。如果是有向图，那么需要根据Kruskal算法的特性来构造邻接矩阵。