C++实现prim算法

可以回答这个问题。Prim算法是一种用于解决最小生成树问题的算法，它的基本思想是从一个点开始，不断扩展生成树的边，直到生成一棵包含所有节点的树，且树的边权和最小。C语言可以通过使用优先队列等数据结构来实现Prim算法。

相关问题

prim算法c++实现

以下是Prim算法的C++实现：

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

const int MAXN = 1001; // 最大点数
const int INF = 0x3f3f3f3f; // 无穷大

struct Edge {
    int to; // 边的终点
    int w; // 边的权值
    Edge(int _to, int _w): to(_to), w(_w) {}
};

vector<Edge> adj[MAXN]; // 邻接表存图
int dist[MAXN]; // 记录每个点到当前生成树的距离
bool vis[MAXN]; // 标记每个点是否已经加入生成树

int Prim(int s) {
    memset(dist, INF, sizeof(dist)); // 初始化距离为无穷大
    memset(vis, false, sizeof(vis)); // 初始化所有点都未加入生成树

    priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq;
    // 小根堆，存储 (点到生成树的最短距离, 点的编号) 的二元组

    dist[s] = 0;
    pq.push(make_pair(0, s)); // 将起点加入堆中

    int ans = 0; // 记录生成树的总权值

    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();

        if (vis[u]) continue; // 如果该点已经加入生成树，则跳过

        vis[u] = true; // 将该点加入生成树

        ans += dist[u]; // 更新生成树的总权值

        for (unsigned int i = 0; i < adj[u].size(); ++i) {
            int v = adj[u][i].to;
            int w = adj[u][i].w;

            if (!vis[v] && w < dist[v]) {
                dist[v] = w;
                pq.push(make_pair(dist[v], v)); // 将 v 加入堆中
            }
        }
    }

    return ans;
}

int main() {
    int n, m;
    cin >> n >> m; // 输入点数和边数

    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w; // 输入一条边的起点、终点和权值
        adj[u].push_back(Edge(v, w));
        adj[v].push_back(Edge(u, w)); // 无向图
    }

    cout << Prim(1) << endl; // 从第一个点开始生成最小生成树

    return 0;
}

该算法的时间复杂度为O(mlogn)，其中n为点数，m为边数。

c++的prim算法代码

### 回答1：
Prim算法是一种用于生成最小生成树的算法。下面是C语言实现的Prim算法代码：

#include <stdio.h>
#define MAX 100
#define INF 0x3f3f3f3f

int graph[MAX][MAX];
int visited[MAX];
int distance[MAX];
int parent[MAX];

void prim(int n) {
    for(int i = 1; i <= n; i++) {
        visited[i] = 0;
        distance[i] = INF;
    }
    distance[1] = 0;
    for(int i = 1; i <= n; i++) {
        int u = 0;
        for(int j = 1; j <= n; j++) {
            if(!visited[j] && (u == 0 || distance[j] < distance[u])) {
                u = j;
            }
        }
        visited[u] = 1;
        for(int v = 1; v <= n; v++) {
            if(graph[u][v] != 0 && !visited[v] && graph[u][v] < distance[v]) {
                distance[v] = graph[u][v];
                parent[v] = u;
            }
        }
    }
    for(int i = 2; i <= n; i++) {
        printf("%d-%d: %d\n", parent[i], i, graph[parent[i]][i]);
    }
}

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= m; i++) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        graph[u][v] = graph[v][u] = w;
    }
    prim(n);
    return 0;
}

注意：这只是一份简单的示例代码，实际应用中可能需要进行改进或优化。

### 回答2：
C语言的Prim算法代码实现如下：

#include <stdio.h>

#define INF 9999  // 定义无穷大

int minKey(int key[], int mstSet[], int n)
{
    int min = INF, min_index;
    for (int v = 0; v < n; v++) {
        if (mstSet[v] == 0 && key[v] < min) {
            min = key[v];
            min_index = v;
        }
    }
    return min_index;
}

void primMST(int graph[][5], int n)
{
    int parent[n];  // 用于存储最小生成树中的父节点
    int key[n];  // 用于存储当前顶点到最小生成树的最小权值

    int mstSet[n];  // 用于记录顶点是否被加入最小生成树

    for (int i = 0; i < n; i++) {
        key[i] = INF;
        mstSet[i] = 0;
    }

    key[0] = 0;   // 选择第一个顶点作为最小生成树的起始顶点
    parent[0] = -1;  // 第一个顶点没有父节点

    for (int count = 0; count < n - 1; count++) {
        int u = minKey(key, mstSet, n);  // 选择key值最小的顶点u加入最小生成树
        mstSet[u] = 1;  // 将顶点u标记为已加入最小生成树

        for (int v = 0; v < n; v++) {
            if (graph[u][v] && mstSet[v] == 0 && graph[u][v] < key[v]) {
                parent[v] = u;
                key[v] = graph[u][v];
            }
        }
    }

    printf("边   权值\n");
    for (int i = 1; i < n; i++) {
        printf("%d - %d    %d\n", parent[i], i, graph[i][parent[i]]);
    }
}

int main()
{
    int graph[5][5] = {{0, 2, 0, 6, 0},
                      {2, 0, 3, 8, 5},
                      {0, 3, 0, 0, 7},
                      {6, 8, 0, 0, 9},
                      {0, 5, 7, 9, 0}};
    primMST(graph, 5);

    return 0;
}

该算法的实现思路是：首先初始化所有顶点的key和mstSet数组，key数组用于记录当前顶点到最小生成树的最小权值，mstSet数组用于记录顶点是否已经被加入最小生成树。然后选择第一个顶点作为最小生成树的起始顶点，循环n-1次，每次将权值最小的顶点加入最小生成树，并更新key和mstSet数组。最后输出最小生成树的边和权值。

### 回答3：
Prim算法是一种用于解决最小生成树问题的贪心算法。它的主要思想是从一个顶点开始，逐步选择边权重最小的边，并将该边所连接的顶点添加到最小生成树中，直到所有顶点都被包括在最小生成树中。

以下是C语言实现的Prim算法代码：

#include <stdio.h>
#include <limits.h>

#define V 5  // 图中顶点的数量

int minKey(int key[], int mstSet[])
{
    int min = INT_MAX, min_index;

    for (int v = 0; v < V; v++)
    {
        if (mstSet[v] == 0 && key[v] < min)
        {
            min = key[v];
            min_index = v;
        }
    }

    return min_index;
}

void printMST(int parent[], int graph[V][V])
{
    printf("边\t权重\n");
    for (int i = 1; i < V; i++)
    {
        printf("%d - %d\t%d\n", parent[i], i, graph[i][parent[i]]);
    }
}

void primMST(int graph[V][V])
{
    int parent[V];
    int key[V];
    int mstSet[V];

    for (int i = 0; i < V; i++)
    {
        key[i] = INT_MAX;
        mstSet[i] = 0;
    }

    key[0] = 0;
    parent[0] = -1;

    for (int count = 0; count < V - 1; count++)
    {
        int u = minKey(key, mstSet);

        mstSet[u] = 1;

        for (int v = 0; v < V; v++)
        {
            if (graph[u][v] && mstSet[v] == 0 && graph[u][v] < key[v])
            {
                parent[v] = u;
                key[v] = graph[u][v];
            }
        }
    }

    printMST(parent, graph);
}

int main()
{
    int graph[V][V] = {
        {0, 2, 0, 6, 0},
        {2, 0, 3, 8, 5},
        {0, 3, 0, 0, 7},
        {6, 8, 0, 0, 9},
        {0, 5, 7, 9, 0},
    };

    primMST(graph);

    return 0;
}

该算法首先定义了一个`minKey`函数，用于选取当前key值最小的顶点。然后使用`printMST`函数打印生成的最小生成树。在`primMST`函数中，首先初始化key数组和mstSet数组，然后选择一个起始顶点，设置其key为0，遍历所有顶点，逐步构建最小生成树。运行代码后，将输出最小生成树的边以及对应的权重。