C++에서 Prim의 알고리즘을 사용하는 방법

제목: C++에서 Prim 알고리즘의 사용법 및 코드 예

소개: Prim 알고리즘은 일반적으로 사용되는 최소 신장 트리 알고리즘으로, 주로 그래프 이론의 최소 신장 트리 문제를 해결하는 데 사용됩니다. C++에서는 합리적인 데이터 구조와 알고리즘 구현을 통해 Prim의 알고리즘을 효과적으로 사용할 수 있습니다. 이 기사에서는 C++에서 Prim의 알고리즘을 사용하는 방법을 소개하고 구체적인 코드 예제를 제공합니다.

1. 프림 알고리즘 소개
프림 알고리즘은 정점에서 시작하여 모든 정점이 포함될 때까지 최소 신장 트리의 정점 집합을 점진적으로 확장하는 그리디 알고리즘입니다. 현재 세트에 연결된 가중치가 가장 작은 Edge를 연속적으로 선택하여 최소 스패닝 트리를 구축합니다.

2. Prim 알고리즘의 구현 단계

1. 빈 최소 스패닝 트리 세트와 우선순위 큐를 생성하여 간선 가중치와 연결된 정점을 저장합니다.
2. 정점을 시작 정점으로 무작위로 선택하고 이를 최소 스패닝 트리 집합에 추가합니다.
3. 시작 정점에 연결된 가장자리를 우선순위 대기열에 추가합니다.
4. 최소 스패닝 트리에 모든 정점이 포함될 때까지 다음 단계를 반복합니다.
   a. 우선순위 대기열에서 가중치가 가장 작은 가장자리와 연결된 정점을 제거합니다.
   b. 정점이 이미 최소 스패닝 트리 집합에 있는 경우 가장자리를 무시합니다.
   c. 그렇지 않으면 정점을 최소 스패닝 트리 집합에 추가하고 정점에 연결된 가장자리를 우선 순위 큐에 추가합니다.
5. 최소 스패닝 트리 집합을 출력합니다.

3. 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 중국어 웹사이트의 기타 관련 기사를 참조하세요!