C++ で Prim のアルゴリズムを使用する方法

タイトル: C での Prim アルゴリズムの使用とコード例

はじめに: Prim アルゴリズムは、一般的に使用される最小スパニング ツリー アルゴリズムであり、主にグラフ理論の問題を解決するために使用されます。スパニングツリーの問題。 C では、適切なデータ構造とアルゴリズムの実装により、Prim のアルゴリズムを効果的に使用できます。この記事では、C で Prim のアルゴリズムを使用する方法と、具体的なコード例を紹介します。

1. Prim アルゴリズムの概要
Prim アルゴリズムは、頂点から開始して、すべての頂点が含まれるまで最小スパニング ツリーの頂点セットを徐々に拡張する貪欲なアルゴリズムです。現在のセットに接続されている最小の重みを持つエッジを継続的に選択することにより、最小スパニング ツリーを構築します。

2. プリム アルゴリズムの実装手順

1. 空の最小スパニング ツリー セットと優先キューを作成して、エッジの重みと接続された頂点を保存します。
2. 頂点を開始頂点としてランダムに選択し、それを最小スパニング ツリー セットに追加します。
3. 開始頂点に接続されているエッジを優先キューに追加します。
4. 最小スパニング ツリーにすべての頂点が含まれるまで、次の手順を繰り返します:
   a. 重みが最小のエッジと接続されている頂点を優先キューから削除します。
   b. 頂点がすでに最小スパニング ツリー セットに含まれている場合は、エッジを無視します。
   c. それ以外の場合は、頂点を最小スパニング ツリー セットに追加し、頂点に接続されているエッジを優先キューに追加します。
5. 最小スパニングツリーセットを出力します。

3. 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;
}

4.
この記事では、C で Prim のアルゴリズムを使用する方法を紹介し、具体的なコード例を示します。最小スパニング ツリーは、適切なデータ構造とアルゴリズム実装を使用することで効率的に計算できます。この記事が、Prim のアルゴリズムを使用して最小スパニング ツリー問題を解決する際に役立つことを願っています。

以上がC++ で Prim のアルゴリズムを使用する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。