Cara menggunakan algoritma pokok rentang minimum dalam C++

Cara menggunakan algoritma pokok rentang minimum dalam C++

Minimum Spanning Tree (MST) ialah konsep penting dalam teori graf Ia mewakili subset tepi yang menghubungkan semua bucu graf tidak berarah berat tepi ini adalah yang paling kecil. Terdapat banyak algoritma yang boleh digunakan untuk menyelesaikan pokok rentang minimum, seperti algoritma Prim dan algoritma Kruskal. Artikel ini akan memperkenalkan cara menggunakan C++ untuk melaksanakan algoritma Prim dan algoritma Kruskal, dan memberikan contoh kod khusus.

Algoritma Prim ialah algoritma tamak Ia bermula dari bucu graf, secara beransur-ansur memilih tepi dengan berat terkecil disambungkan ke pokok rentang minimum semasa, dan menambah tepi kepada pokok rentang minimum. Berikut ialah contoh kod C++ bagi algoritma Prim:

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

const int INF = 1e9;

int prim(vector<vector<pair<int, int>>>& graph) {
    int n = graph.size(); // 图的顶点数
    vector<bool> visited(n, false); // 标记顶点是否已访问
    vector<int> dist(n, INF); // 记录顶点到最小生成树的最短距离
    int minCost = 0; // 最小生成树的总权值

    // 从第一个顶点开始构建最小生成树
    dist[0] = 0;

    // 使用优先队列保存当前距离最小的顶点和权值
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push(make_pair(0, 0));

    while (!pq.empty()) {
        int u = pq.top().second; // 当前距离最小的顶点
        pq.pop();

        // 如果顶点已访问过，跳过
        if (visited[u]) {
            continue;
        }

        visited[u] = true; // 标记顶点为已访问
        minCost += dist[u]; // 加入顶点到最小生成树的权值

        // 对于顶点u的所有邻接顶点v
        for (auto& edge : graph[u]) {
            int v = edge.first;
            int weight = edge.second;

            // 如果顶点v未访问过，并且到顶点v的距离更小
            if (!visited[v] && weight < dist[v]) {
                dist[v] = weight;
                pq.push(make_pair(dist[v], v));
            }
        }
    }

    return minCost;
}

int main() {
    int n, m; // 顶点数和边数
    cin >> n >> m;
    vector<vector<pair<int, int>>> graph(n);

    // 读取边的信息
    for (int i = 0; i < m; ++i) {
        int u, v, w; // 边的两个顶点及其权值
        cin >> u >> v >> w;
        --u; --v; // 顶点从0开始编号
        graph[u].push_back(make_pair(v, w));
        graph[v].push_back(make_pair(u, w));
    }

    int minCost = prim(graph);
    cout << "最小生成树的权值之和为：" << minCost << endl;

    return 0;
}

Algoritma Kruskal ialah algoritma tamak berasaskan tepi Ia memilih tepi dengan berat terkecil daripada semua tepi graf dan menentukan sama ada tepi akan membentuk kitaran. Jika tiada kitaran terbentuk, tambahkan tepi pada pokok rentang minimum. Berikut ialah contoh kod C++ bagi algoritma Kruskal:

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

struct Edge {
    int u, v, weight; // 边的两个顶点及其权值
    Edge(int u, int v, int weight) : u(u), v(v), weight(weight) {}
};

const int MAXN = 100; // 最大顶点数
int parent[MAXN]; // 并查集数组

bool compare(Edge a, Edge b) {
    return a.weight < b.weight;
}

int findParent(int x) {
    if (parent[x] == x) {
        return x;
    }
    return parent[x] = findParent(parent[x]);
}

void unionSet(int x, int y) {
    int xParent = findParent(x);
    int yParent = findParent(y);
    if (xParent != yParent) {
        parent[yParent] = xParent;
    }
}

int kruskal(vector<Edge>& edges, int n) {
    sort(edges.begin(), edges.end(), compare);
    int minCost = 0; // 最小生成树的总权值

    for (int i = 0; i < n; ++i) {
        parent[i] = i; // 初始化并查集数组
    }

    for (auto& edge : edges) {
        int u = edge.u;
        int v = edge.v;
        int weight = edge.weight;

        // 如果顶点u和顶点v不属于同一个连通分量，则将该边加入到最小生成树中
        if (findParent(u) != findParent(v)) {
            unionSet(u, v);
            minCost += weight;
        }
    }

    return minCost;
}

int main() {
    int n, m; // 顶点数和边数
    cin >> n >> m;
    vector<Edge> edges;

    // 读取边的信息
    for (int i = 0; i < m; ++i) {
        int u, v, w; // 边的两个顶点及其权值
        cin >> u >> v >> w;
        edges.push_back(Edge(u, v, w));
    }

    int minCost = kruskal(edges, n);
    cout << "最小生成树的权值之和为：" << minCost << endl;

    return 0;
}

Melalui contoh kod di atas, kita boleh menggunakan algoritma Prim dan algoritma Kruskal untuk menyelesaikan masalah pokok rentang minimum dalam C++. Dalam aplikasi praktikal, algoritma yang sesuai boleh dipilih untuk menyelesaikan masalah mengikut situasi tertentu. Kerumitan masa bagi algoritma ini masing-masing ialah O(ElogV) dan O(ElogE), di mana V ialah bilangan bucu dan E ialah bilangan tepi. Oleh itu, mereka juga boleh mencapai hasil yang lebih baik apabila memproses graf berskala besar.

Atas ialah kandungan terperinci Cara menggunakan algoritma pokok rentang minimum dalam C++. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!