为什么最小生成树邻接矩阵加起来除以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;
}

破圈法实现最小生成树邻接矩阵存储C++

破圈法（Kruskal's Algorithm），也称为贪心算法，是一种用于求解无向加权图中最小生成树的算法。在邻接矩阵表示的图中，它通过一次遍历边集合，每次选择当前未加入生成树的最短边，直到所有顶点都被连接起来形成一棵树。

以下是使用C++实现破圈法的步骤：

#include <vector>
#include <algorithm>

// 图的邻接矩阵表示
typedef int Weight;
struct Edge {
    int src, dest;
    Weight weight;
};

bool compareEdges(Edge a, Edge b) { // 边比较函数，按权重从小到大排序
    return a.weight < b.weight;
}

std::vector<Edge> kruskalMST(const std::vector<std::vector<Weight>>& graph, int n) {
    std::vector<Edge> edges; // 存储所有边
    for (int i = 0; i < n; ++i)
        for (int j = i + 1; j < n; ++j)
            edges.push_back({i, j, graph[i][j]});

    sort(edges.begin(), edges.end(), compareEdges); // 排序

    std::vector<int> parent(n, -1); // 妥善初始化父节点数组
    std::vector<bool> visited(n, false);

    std::vector<Edge> mst; // 最小生成树
    for (const auto& edge : edges) {
        int u = edge.src, v = edge.dest;
        if (parent[u] == -1 && parent[v] == -1) { // 如果两个端点均未访问
            mst.push_back(edge);
            parent[u] = v;
            parent[v] = u;
        } else if (parent[u] != -1 && parent[u] != v) { // 如果u已经连接了v的父亲
            // 形成了环，跳过这条边
        }
    }

    return mst;
}