Comment utiliser l'algorithme d'arbre couvrant minimum en C++

Comment utiliser l'algorithme du spanning tree minimum en C++

Le minimum spanning tree (MST) est un concept important dans la théorie des graphes. Il représente le sous-ensemble des arêtes reliant tous les sommets d'un graphe connecté non orienté. le poids de ces arêtes est le plus petit. Il existe de nombreux algorithmes qui peuvent être utilisés pour résoudre l'arbre couvrant minimum, tels que l'algorithme de Prim et l'algorithme de Kruskal. Cet article présentera comment utiliser C++ pour implémenter l'algorithme de Prim et l'algorithme de Kruskal, et donnera des exemples de code spécifiques.

L'algorithme de Prim est un algorithme glouton. Il part d'un sommet du graphique, sélectionne progressivement l'arête avec le plus petit poids connecté à l'arbre couvrant minimum actuel et ajoute l'arête à l'arbre couvrant minimum. Voici un exemple de code C++ de l'algorithme de 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;
}

L'algorithme de Kruskal est un algorithme glouton basé sur les arêtes. Il sélectionne l'arête ayant le plus petit poids parmi toutes les arêtes du graphique et détermine si l'arête formera un cycle. Si aucun cycle n’est formé, ajoutez l’arête à l’arbre couvrant minimum. Ce qui suit est un exemple de code C++ de l'algorithme de 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;
}

Grâce à l'exemple de code ci-dessus, nous pouvons utiliser l'algorithme de Prim et l'algorithme de Kruskal pour résoudre le problème de l'arbre couvrant minimum en C++. Dans les applications pratiques, l'algorithme approprié peut être sélectionné pour résoudre le problème en fonction de la situation spécifique. La complexité temporelle de ces algorithmes est respectivement O(ElogV) et O(ElogE), où V est le nombre de sommets et E est le nombre d'arêtes. Par conséquent, ils peuvent également obtenir de meilleurs résultats lors du traitement de graphiques à grande échelle.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!