C++代码实现 Prim 算法 |21xrx.com

C++代码实现 Prim 算法

2023-06-25 16:43:55 深夜i -- --

C++ Prim算法算法实现图论最小生成树

Prim算法是一种经典的求解最小生成树问题的算法，其基本思想是从一个点开始，每次找到距离它最近的未加入最小生成树中的点，即可得到最小生成树。下面我们将介绍如何使用C++语言实现Prim算法。

1. 数据结构

首先，我们需要定义若干个数据结构，包括：

1）图的邻接表表示法：通过链表的形式来存储所有点和边的信息，便于快速的插入点和边以及查找指定点或边的信息。

2）最小堆：使用最小堆来存储各个点的权重，以便于快速的找到距离当前点的最近点。

3）布尔标记：将每个点标记为已加入最小生成树或未加入最小生成树。

2. Prim算法实现代码

基于以上的数据结构，我们可以编写Prim算法的实现代码。

首先，我们需要实现一个用来读取输入数据并构造图的函数：


vector<pair<int, int>> adj[10000];  // 图的邻接表表示法
void add_edge(int u, int v, int w)
{
  adj[u].push_back(make_pair(v, w));  // 在 u 的邻接表中添加一条到 v 的边
  adj[v].push_back(make_pair(u, w));  // 在 v 的邻接表中添加一条到 u 的边
}
int main()
{
  int n, m;    // n表示点数，m表示边数
  cin >> n >> m;
  for (int i = 0; i < m; ++i)
  {
    int u, v, w;
    cin >> u >> v >> w;
    add_edge(u, v, w);   // 添加一条边
  }
  // Prim 算法
  // ...
  return 0;
}

接着，我们需要实现Prim算法的核心部分：


int n;  // 点数
int m;  // 边数
int vis[10000];  // 标记数组，如果 vis[i] 为 true，则表示第 i 个点已经在生成树中了
int dis[10000];  // 距离数组，以当前点为起点到各个点的距离
int ans = 0;  // 最小生成树的总权值
void prim()
{
  // 初始化 dis 数组，给每个点赋一个很大的值
  for (int i = 0; i < n; ++i)
  {
    dis[i] = INT_MAX;
  }
  dis[0] = 0;  // 将起点的距离设为 0
  priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;  // 定义一个最小堆
  q.push(make_pair(dis[0], 0));  // 将起点加入最小堆
  // 循环直到堆为空
  while (!q.empty())
  {
    int u, d;
    // 取出堆顶的元素
    u = q.top().second;
    d = q.top().first;
    q.pop();
    // 判断是否已经处理过，如果已经处理过则 continue
    if (vis[u] == true) continue;
    vis[u] = true;
    // 更新 ans 的值
    ans += d;
    // 更新 dis 数组
    for (int i = 0; i < adj[u].size(); ++i)
    {
      int v = adj[u][i].first;
      int w = adj[u][i].second;
      if (vis[v] == false && w < dis[v])
      {
        dis[v] = w;
        q.push(make_pair(dis[v], v));
      }
    }
  }
  cout << ans << endl;
}

3. 总结

通过以上代码，我们可以实现Prim算法，并得到最小生成树的总权值。当然，如果我们需要输出每个点与其父节点的连线，我们可以在prim()函数的 while 循环中加入一些代码来完成。另外，在实际项目中，由于数据规模可能非常大，我们还可以通过加入剪枝等优化方式来加快Prim算法的执行速度。

上一篇: idea打包java可执行jar包

下一篇: Node.js eval函数原理及安全性分析

评论区

()

相似文章