標題：C 中Prim演算法的使用及程式碼範例
引言：Prim演算法是一種常用的最小生成樹演算法，主要用於解決圖論中的最小生成樹問題。在C 中，透過合理的資料結構和演算法實現，可以有效地使用Prim演算法。本文將介紹如何在C 中使用Prim演算法，並提供具體的程式碼範例。
一、Prim演算法簡介
Prim演算法是一種貪心演算法，它從一個頂點開始，逐步擴展最小生成樹的頂點集合，直到包含所有頂點。它透過不斷選擇與當前集合相連的最小權重的邊來建立最小生成樹。
二、Prim演算法的實作步驟
三、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中文網其他相關文章！
