21xrx.com
2024-12-23 01:44:23 Monday
登录
文章检索 我的文章 写文章
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']}}
()
回复
回复