Cara menggunakan algoritma Prim dalam C++

Tajuk: Contoh penggunaan dan kod algoritma Prim dalam C++

Pengenalan: Algoritma Prim ialah algoritma pokok rentang minimum yang biasa digunakan, terutamanya digunakan untuk menyelesaikan masalah pokok rentang minimum dalam teori graf. Dalam C++, algoritma Prim boleh digunakan dengan berkesan melalui struktur data yang munasabah dan pelaksanaan algoritma. Artikel ini akan memperkenalkan cara menggunakan algoritma Prim dalam C++ dan memberikan contoh kod khusus.

1. Pengenalan kepada algoritma Prim
Algoritma prim ialah algoritma tamak yang bermula dari bucu dan secara beransur-ansur mengembangkan set bucu pokok rentang minimum sehingga semua bucu dimasukkan. Ia membina pokok rentang minimum dengan terus memilih tepi dengan berat terkecil yang disambungkan ke set semasa.

2. Langkah pelaksanaan algoritma Prim

1. Buat set pokok rentang minimum kosong dan baris gilir keutamaan untuk menyimpan pemberat tepi dan bucu bersambung.
2. Pilih bucu secara rawak sebagai bucu permulaan dan tambahkannya pada set pokok rentang minimum.
3. Tambahkan tepi yang disambungkan ke bucu permulaan pada barisan keutamaan.
4. Ulang langkah berikut sehingga pokok rentang minimum mengandungi semua bucu:
   a.
   b. Jika bucu sudah berada dalam set pokok rentang minimum, abaikan bahagian tepi.
   c. Jika tidak, tambahkan bucu pada set pokok rentang minimum dan tambahkan tepi yang disambungkan ke bucu pada barisan keutamaan.
5. Keluarkan set pokok rentang minimum.

3. Contoh kod C++
Berikut ialah contoh kod menggunakan C++ untuk melaksanakan algoritma Prim, yang menggunakan matriks bersebelahan untuk mewakili graf:

#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. dan menyediakan contoh kod perenggan tertentu. Pepohon rentang minimum boleh dikira dengan cekap dengan menggunakan struktur data dan pelaksanaan algoritma yang sesuai. Saya harap artikel ini akan membantu anda apabila menggunakan algoritma Prim untuk menyelesaikan masalah pokok rentang minimum.

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