How to use Prim's algorithm in C++

Title: Use of Prim algorithm and code examples in C

Introduction: Prim algorithm is a commonly used minimum spanning tree algorithm, mainly used to solve graph theory problems The minimum spanning tree problem. In C, Prim's algorithm can be used effectively with proper data structures and algorithm implementation. This article will introduce how to use Prim's algorithm in C and provide specific code examples.

1. Introduction to Prim algorithm
The Prim algorithm is a greedy algorithm that starts from a vertex and gradually expands the vertex set of the minimum spanning tree until all vertices are included. It builds a minimum spanning tree by continuously selecting the edge with the smallest weight connected to the current set.

2. Implementation steps of Prim algorithm

1. Create an empty minimum spanning tree set and a priority queue to store edge weights and connected vertices.
2. Randomly select a vertex as the starting vertex and add it to the minimum spanning tree set.
3. Add the edge connected to the starting vertex to the priority queue.
4. Repeat the following steps until the minimum spanning tree contains all vertices:
   a. Remove the edge with the smallest weight and the connected vertices from the priority queue.
   b. If the vertex is already in the minimum spanning tree set, ignore the edge.
   c. Otherwise, add the vertex to the minimum spanning tree set and add the edges connected to the vertex to the priority queue.
5. Output the minimum spanning tree set.

3. C code example
The following is a code example using C to implement Prim's algorithm, which uses an adjacency matrix to represent the graph:

#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. Summary
This article Introduces how to use Prim's algorithm in C and provides a specific code example. Minimum spanning trees can be computed efficiently by using appropriate data structures and algorithm implementations. I hope this article will be helpful to you when using Prim's algorithm to solve the minimum spanning tree problem.

The above is the detailed content of How to use Prim's algorithm in C++. For more information, please follow other related articles on the PHP Chinese website!