Comment utiliser l'algorithme de Prim en C++

Titre : Exemples d'utilisation et de code de l'algorithme Prim en C++

Introduction : L'algorithme Prim est un algorithme d'arbre couvrant minimum couramment utilisé, principalement utilisé pour résoudre le problème de l'arbre couvrant minimum dans la théorie des graphes. En C++, l'algorithme de Prim peut être utilisé efficacement grâce à des structures de données raisonnables et à la mise en œuvre de l'algorithme. Cet article explique comment utiliser l'algorithme de Prim en C++ et fournit des exemples de code spécifiques.

1. Introduction à l'algorithme Prim
L'algorithme Prim est un algorithme glouton qui part d'un sommet et étend progressivement l'ensemble de sommets de l'arbre couvrant minimum jusqu'à ce que tous les sommets soient inclus. Il construit un arbre couvrant minimum en sélectionnant continuellement l'arête avec le plus petit poids connecté à l'ensemble actuel.

2. Étapes de mise en œuvre de l'algorithme Prim

1. Créez un ensemble d'arbres couvrant minimum vide et une file d'attente prioritaire pour stocker les poids des bords et les sommets connectés.
2. Sélectionnez au hasard un sommet comme sommet de départ et ajoutez-le à l'ensemble minimal d'arbres couvrants.
3. Ajoutez l'arête connectée au sommet de départ à la file d'attente prioritaire.
4. Répétez les étapes suivantes jusqu'à ce que l'arbre couvrant minimum contienne tous les sommets :
   a. Supprimez l'arête ayant le plus petit poids et les sommets connectés de la file d'attente prioritaire.
   b. Si le sommet est déjà dans l'ensemble minimal d'arbre couvrant, ignorez l'arête.
   c. Sinon, ajoutez le sommet à l'ensemble minimal d'arbre couvrant et ajoutez les arêtes connectées au sommet à la file d'attente prioritaire.
5. Sortez l'ensemble minimal d'arbre couvrant.

3. Exemple de code C++
Ce qui suit est un exemple de code utilisant C++ pour implémenter l'algorithme de Prim, qui utilise une matrice de contiguïté pour représenter le graphique :

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

const int MAX = 100;
const int INF = 9999;

vector<vector<int>> graph(MAX, vector<int>(MAX, INF));

void prim(int start, int n)
{
    vector<int> key(n, INF);  // 存储每个顶点到最小生成树的最小权重
    vector<bool> visited(n, false);  // 标记顶点是否已经加入最小生成树
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;  // 优先队列，按权重升序排列

    key[start] = 0;  // 起始顶点到自身的权重置为0
    pq.push(make_pair(0, start));

    while (!pq.empty())
    {
        int u = pq.top().second;
        pq.pop();

        visited[u] = true;

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

    // 输出最小生成树的边
    for (int i = 1; i < n; i++)
    {
        cout << "Edge: " << i << " - " << key[i] << endl;
    }
}

int main()
{
    int n, e;
    cout << "Enter the number of vertices: ";
    cin >> n;
    cout << "Enter the number of edges: ";
    cin >> e;

    cout << "Enter the edges and weights: " << endl;
    int u, v, w;
    for (int i = 0; i < e; i++)
    {
        cin >> u >> v >> w;
        graph[u][v] = w;
        graph[v][u] = w;
    }

    int start;
    cout << "Enter the starting vertex: ";
    cin >> start;

    cout << "Minimum Spanning Tree edges: " << endl;
    prim(start, n);

    return 0;
}

4.Résumé
Cet article présente comment utiliser l'algorithme de Prim en C++, et fournit un exemple de code de paragraphe détaillé. Les arbres couvrants minimaux peuvent être calculés efficacement en utilisant des structures de données et des implémentations d'algorithmes appropriées. J'espère que cet article vous sera utile lorsque vous utiliserez l'algorithme de Prim pour résoudre le problème de l'arbre couvrant minimum.

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!