如何使用C++中的Prim演算法

標題：C 中Prim演算法的使用及程式碼範例

引言：Prim演算法是一種常用的最小生成樹演算法，主要用於解決圖論中的最小生成樹問題。在C 中，透過合理的資料結構和演算法實現，可以有效地使用Prim演算法。本文將介紹如何在C 中使用Prim演算法，並提供具體的程式碼範例。

一、Prim演算法簡介
Prim演算法是一種貪心演算法，它從一個頂點開始，逐步擴展最小生成樹的頂點集合，直到包含所有頂點。它透過不斷選擇與當前集合相連的最小權重的邊來建立最小生成樹。

二、Prim演算法的實作步驟

1. 建立一個空的最小生成樹集合和一個優先佇列，用於儲存邊的權重和相連的頂點。
2. 隨機選擇一個頂點作為起始頂點，並將其加入最小生成樹集合。
3. 將與起始頂點相連的邊加入優先隊列。
4. 重複下列步驟直到最小生成樹包含所有頂點：
   a. 從優先佇列中取出權重最小的邊和相連的頂點。
   b. 如果該頂點已經在最小生成樹集合中，則忽略該邊。
   c. 否則，將該頂點加入最小生成樹集合，並將與該頂點相連的邊加入優先隊列。
5. 輸出最小生成樹集合。

三、C 程式碼範例
下面是使用C 實作Prim演算法的程式碼範例，其中使用了鄰接矩陣表示圖：

#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;
}

四、總結
本文介紹了C 中如何使用Prim演算法，並提供了一段具體的程式碼範例。透過使用合適的資料結構和演算法實現，可以有效地計算最小生成樹。希望本文對您在使用Prim演算法解決最小生成樹問題時有所幫助。

以上是如何使用C++中的Prim演算法的詳細內容。更多資訊請關注PHP中文網其他相關文章！