算法与数据结构--最小生成树算法

一.应用的场景

类似于这种最小成本问题，实际上就是计算加权图把所有点连起来权重之和最小值的时候是怎么连接的。类似的问题还有最短耗时之类的问题。

二.最小生成树的定义

生成树：
图的生成树是它的一颗含有其所有顶点的无环连通子图。
【简单说就是所有顶点连接在一起，并且没有环。
因此有n个顶点，n-1的边】
最小生成树：
所有生成树中权值(树中所有边的权重之和)最小的生成树。

解决之类问题实际上就是求出最小生成树，并计算它的权值之和。

三.如何构建最小生成树

目前有两种经典的生成最小生成树的算法，Prim算法和Kruskal算法。两种算法都是基于贪婪算法的思想。

1.Kruskal算法

【1】将所有边按照权值从小到大进行排序。
【2】依次取出每条边，如果边的两个节点分别位于两棵树上，则将这两棵树合并成为一棵树；如果两个节点位于同一棵树上，则忽略这条边。
【3】等到所有的边都遍历结束之后，如果所有的生成树可以合并成一棵生成树，那么它就是我们需要寻找的最小生成树，反之则没有最小生成树。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 结构体表示一条边
struct Edge {
    int src, dest, weight;//起点，终点，权值 
};

// 结构体表示并查集
struct DisjointSet {
	//parent 数组存储每个元素的父节点，rank 数组存储每个集合的秩。
    vector<int> parent, rank;
    
    // 构造函数，初始化并查集
    DisjointSet(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];
    }
    
    // 合并两个集合，使用秩优化
    void unionSets(int x, int y) {
        int xRoot = find(x);
        int yRoot = find(y);
        
        if (rank[xRoot] < rank[yRoot]) {
            parent[xRoot] = yRoot;
        } else if (rank[xRoot] > rank[yRoot]) {
            parent[yRoot] = xRoot;
        } else {
            parent[yRoot] = xRoot;
            rank[xRoot]++;
        }
    }
};

// 比较函数，用于对边按权值进行排序
bool compareEdges(const Edge& a, const Edge& b) {
    return a.weight < b.weight;
}

// 使用Kruskal算法求解最小生成树
vector<Edge> kruskalMST(vector<Edge>& edges, int numVertices) {
    // 对边按权值进行排序
    sort(edges.begin(), edges.end(), compareEdges);
    
    vector<Edge> result;
    DisjointSet ds(numVertices);
    
    for (const Edge& edge : edges) {
        int srcParent = ds.find(edge.src);
        int destParent = ds.find(edge.dest);
        
        // 如果加入这条边不会形成环路，则将它加入最小生成树
        if (srcParent != destParent) {
            result.push_back(edge);
            ds.unionSets(srcParent, destParent);
        }
    }
    
    return result;
}

// 打印最小生成树的边集
void printMST(const vector<Edge>& mst) {
    cout << "最小生成树：" << endl;
    for (const Edge& edge : mst) {
        cout << edge.src << " -- " << edge.dest << " : " << edge.weight << endl;
    }
}

int main() {
    int numVertices, numEdges;
    cout << "请输入顶点数：";
    cin >> numVertices;
    cout << "请输入边数：";
    cin >> numEdges;
    
    vector<Edge> edges(numEdges);
    
    cout << "请输入每条边的起点、终点和权值：" << endl;
    for (int i = 0; i < numEdges; i++) {
        cin >> edges[i].src >> edges[i].dest >> edges[i].weight;
    }
    
    vector<Edge> mst = kruskalMST(edges, numVertices);
    
    printMST(mst);
    
    return 0;
}

2.Prim算法

思路：

最优布线问题 题解_学校有 n 台计算机,为了方便数据传输,现要将它们用数据线连接起来。两台计算机被-CSDN博客

代码：

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

const int INF = 1e9; // 定义无穷大

// 表示图的邻接矩阵
vector<vector<int>> graph;

// 使用Prim算法生成最小生成树
void prim(int n)
{
    vector<int> dist(n, INF); // 存储顶点到最小生成树的距离
    vector<bool> visited(n, false); // 记录顶点是否被访问过
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; // 小顶堆

    int src = 0; // 从顶点0开始生成最小生成树
    dist[src] = 0;
    pq.push(make_pair(0, src));

    while (!pq.empty())
    {
        int u = pq.top().second;
        pq.pop();
        visited[u] = true;

        for (int v = 0; v < n; ++v)
        {
            if (graph[u][v] != 0 && !visited[v] && graph[u][v] < dist[v])
            {
                dist[v] = graph[u][v];
                pq.push(make_pair(dist[v], v));
            }
        }
    }

    cout << "边\t权值" << endl;
    for (int i = 1; i < n; ++i)
    {
        cout << i << " - " << i + 1 << "\t" << dist[i] << endl;
    }
}

int main()
{
    int n; // 顶点数量
    cout << "请输入顶点数量: ";
    cin >> n;

    // 初始化邻接矩阵
    graph.resize(n, vector<int>(n));
    cout << "请输入邻接矩阵:" << endl;
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            cin >> graph[i][j];
        }
    }

    prim(n);

    return 0;
}