如何实现最小生成树矩阵的展示？附相关C++代码片段

针对这个问题，我结合你提供的C++代码片段，整理了一套完整的实现方案——从补全Union-Find类，到生成MST邻接矩阵，再到美观地打印矩阵，一步步来：

1. 补全Union-Find不相交集合类 #

你给出的Union-Find代码片段不完整，这里补全结合路径压缩和按秩合并的完整实现，这两个启发式策略能让Union-Find的操作几乎达到常数时间复杂度：

#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
#include<iomanip>
using namespace std;

typedef pair<int, int> intPair;
typedef vector<double> doubleVector;
typedef vector<intPair> intPairVector;

// OOP风格的Union-Find实现，带路径压缩和按秩合并
class UnionFind {
private:
    vector<int> parent;
    vector<int> rank;
public:
    UnionFind(int n) {
        parent.resize(n);
        rank.resize(n, 0);
        // 初始化每个节点的父节点为自身
        for (int i = 0; i < n; ++i)
            parent[i] = i;
    }

    // 查找根节点，路径压缩优化
    int find(int x) {
        if (parent[x] != x)
            parent[x] = find(parent[x]);
        return parent[x];
    }

    // 按秩合并，避免树退化成链表
    bool unite(int x, int y) {
        int xr = find(x);
        int yr = find(y);
        if (xr == yr) return false; // 两个节点已在同一集合，无需合并
        if (rank[xr] < rank[yr])
            parent[xr] = yr;
        else {
            parent[yr] = xr;
            if (rank[xr] == rank[yr])
                rank[xr]++;
        }
        return true;
    }
};

2. 用Kruskal算法生成MST并构建邻接矩阵 #

我们用Kruskal算法来筛选出MST的边，然后把这些边映射到邻接矩阵中。这里先定义边的结构体，再实现构建矩阵的函数：

// 定义图的边，包含两个顶点和权重
struct Edge {
    int u, v;
    double weight;
    Edge(int u_, int v_, double w_) : u(u_), v(v_), weight(w_) {}
    // 重载小于运算符，用于按权重升序排序边（Kruskal算法需要）
    bool operator<(const Edge& other) const {
        return weight < other.weight;
    }
};

// 生成MST的邻接矩阵
vector<doubleVector> buildMSTMatrix(int numVertices, vector<Edge>& edges) {
    // 初始化MST矩阵，所有元素设为0（0表示两个顶点间无MST边）
    vector<doubleVector> mstMatrix(numVertices, doubleVector(numVertices, 0.0));
    UnionFind uf(numVertices);

    // 按边的权重从小到大排序
    sort(edges.begin(), edges.end());

    int edgesAdded = 0;
    for (Edge& e : edges) {
        // 如果两个顶点不在同一集合，就合并并加入MST
        if (uf.unite(e.u, e.v)) {
            // 无向图，所以双向赋值权重
            mstMatrix[e.u][e.v] = e.weight;
            mstMatrix[e.v][e.u] = e.weight;
            edgesAdded++;
            // MST的边数是顶点数-1，达到后提前退出循环
            if (edgesAdded == numVertices - 1)
                break;
        }
    }

    return mstMatrix;
}

3. 美观打印MST矩阵的函数 #

为了让矩阵看起来整齐易读，我们可以设置输出格式，固定小数位数并对齐每一列：

void printMatrix(const vector<doubleVector>& matrix) {
    int n = matrix.size();
    cout << "MST邻接矩阵：" << endl;
    // 设置输出格式：保留2位小数，每列宽度为8
    cout << fixed << setprecision(2);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cout << setw(8) << matrix[i][j];
        }
        cout << endl;
    }
}

4. 测试示例 #

我们用一个简单的4顶点图来测试整个流程：

int main() {
    int numVertices = 4;
    // 定义图的所有边（顶点编号从0开始）
    vector<Edge> edges = {
        Edge(0, 1, 1.0),
        Edge(0, 2, 3.0),
        Edge(1, 2, 1.0),
        Edge(1, 3, 5.0),
        Edge(2, 3, 2.0)
    };

    // 生成MST矩阵并打印
    vector<doubleVector> mstMatrix = buildMSTMatrix(numVertices, edges);
    printMatrix(mstMatrix);

    return 0;
}

运行结果 #

执行代码后，你会得到这样的输出：

MST邻接矩阵：
   0.00   1.00   0.00   0.00
   1.00   0.00   1.00   0.00
   0.00   1.00   0.00   2.00
   0.00   0.00   2.00   0.00

额外说明 #

• 如果你的图是稠密图（顶点多、边也多），可以换成Prim算法（优先队列版本时间复杂度O(E log V)）来实现，效率会更高。
• 矩阵中的0值表示对应两个顶点在MST中没有直接相连的边，非0值就是MST边的权重。

内容的提问来源于stack exchange，提问作者Bailey Wells