21xrx.com
2024-11-05 14:39:59 Tuesday
登录
文章检索 我的文章 写文章
C++最小生成树Prim算法：详解及示例代码
2023-06-29 16:38:23 深夜i     --     --
C++ 最小生成树 Prim算法 详解 示例代码

在图论中，生成树是指一个图的一颗子树，它包含该图的所有顶点，但是只有足够数量的边来连接它们。最小生成树是指连接图中所有顶点的一颗生成树，使得树上所有边的长度之和最小。

Prim算法是一种常用的求解最小生成树的算法，其基本思想是从任意一个节点开始，逐步向该节点所在的连通块中添加边，最终形成一颗最小生成树。或者说，算法从一个包含任意一点的树开始，向其扩张并选择新加入的边满足目标要求。

下面我们就来详细介绍C++中Prim算法的实现及常用的代码模板。

C++ Prim算法思路：

1. 我们首先选定一个起始节点，并将其加入已知树中，任意选定一个节点作为起点，并将与该节点相邻的边（也即是连接树中节点和非树中节点的边）加入待选择的候选边集中。

2. 选择与新加入的节点权值最小的边，根据Prim算法的贪心思想，我们需要优先选择已知树中的节点和非树中节点之间权值最小的边，则会将该边加入到已知树中，并将所选节点标记为已知。

3. 将新加入的节点以及与其相邻的边加入到已知树中，此时已在树中的节点不再是初始节点，而是一步步地加入的节点。

4. 重复第2-3步，直至树中节点数等于总节点数。

C++ Prim算法实现示例代码：

为了让读者更好的理解Prim算法如何实现，我们在这里提供一份C++的示例代码，读者可以阅读代码并修改参数来进一步理解该算法实现的细节。



#include<iostream>


#include<cstdio>


#include<cstring>


#include<algorithm>


using namespace std;


const int N = 500010;


struct node {


  int tx, ty, tz;


  bool operator<(const node &X) const


    return tz < X.tz;


  


} p[N];


int n, m;


int h[N], e[N], ne[N], w[N], idx;


bool vis[N];


int dist[N];


void add(int a, int b, int c) {


  e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;


  e[idx] = a, ne[idx] = h[b], w[idx] = c, h[b] = idx++; 


}


void prim() {


  memset(dist, 0x3f, sizeof dist);


  dist[1] = 0;


  for(int i = 0; i < n; i++) {


    int t = -1;


    for(int j = 1; j <= n; j++)


      if(!vis[j] && (t == -1 || dist[t] > dist[j])) t = j;


    vis[t] = true;


    for(int j = h[t]; ~j; j = ne[j]) {


      int k = e[j];


      if(vis[k]) continue;


      if(dist[k] > w[j]) dist[k] = w[j];


    }


  }


}


int main() {


  scanf("%d%d", &n, &m);


  memset(h, -1, sizeof h);


  for(int i = 0; i < m; i++)


    scanf("%d%d%d", &p[i].tx, &p[i].ty, &p[i].tz);


  sort(p, p+m); 


  for(int i = 0, cnt = 0; cnt < n-1 && i < m; i++) {


    int a = p[i].tx, b = p[i].ty, c = p[i].tz;


    int sa = find(a), fa = find(b);


    if(sa != fa) {


      add(a, b, c);


      add(b, a, c);


      fa[fa] = sa; 


      cnt++; 


    }


  } 


  prim();


  int res = 0;


  for(int i = 1; i <= n; i++)


    res += dist[i];


  printf("%d", res);


  return 0;


}

代码解释：

上述代码中，我们首先需要定义一个边结构体，来存放树中节点间的边。在示例代码中，我们定义了一个结构体node，包含了tx、ty、tz三个参数，tx和ty分别为树中节点的编号，tz则是这两个节点之间边的权值。

接下来，我们需要定义一些基本变量和数据结构。在这段代码中，我们定义了n、m、idx、h、e、ne、w、vis以及dist这几个变量和数据结构，分别为图的节点数、边数、邻接表的相关信息，访问标记以及距离数组。需要注意的是，dist数组被初始化为无穷大，而在求解过程中，dist[i]存储的是起点到i这个节点的最短距离。

然后，我们可以对主函数中描述的连通图进行解析，并将边按照权值排序。之后，根据Prim算法的基本思想，我们需要将一个初始节点加入已知树中，并将与该节点相邻的边加入待选择的边集中。因此，代码中select(1)表示选择1号节点作为初始节点，并将与其相邻的边加入待选择边集中。之后，代码中提供的prim()函数就是实现具体Prim算法的核心函数。其中，for循环遍历所有非树中节点，并选出权值最小的一条边进行选择。然后，继续选择新加入节点以及与其相邻的边加入已知树中。最终，我们可以求解出最小生成树，即可得到图中所有节点间的最短路径。

  
  

评论区

{{item['qq_nickname']}}
()
回复
回复