使用C++实现Prim算法 |21xrx.com

使用C++实现Prim算法

2023-07-04 19:16:25 深夜i -- --

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

Prim算法是一种求解最小生成树的常见算法，它的基本思想是从一个节点开始，逐步扩展生成树的大小，直到覆盖所有节点为止。在这个过程中，每次选择距离当前生成树最近的节点，加入生成树中。通过这样的方式，就能够得到一个最小的生成树。下面，我们来看一下如何使用C++实现Prim算法。

首先，我们需要定义一个结构体来表示每个节点。这个结构体包含两个成员变量，一个是节点的编号，一个是节点到生成树的最短距离。代码如下：


struct Node
  int id;
  int dist;
;

在实现Prim算法的过程中，我们需要使用最小堆来选取离当前生成树最近的节点。因此，我们需要定义一个比较函数来比较两个节点之间的距离。代码如下：


struct cmp
{
  bool operator () (Node a, Node b)
  
    return a.dist > b.dist;
  
};

接下来，我们需要实现Prim算法的核心部分。具体而言，我们需要从源节点开始，逐步扩展生成树。在这个过程中，我们需要使用最小堆来选取距离当前生成树最近的节点。代码如下：


void prim(int n, vector<vector<int>>& graph)
{
  vector<int> dist(n, INT_MAX);
  vector<bool> vis(n, false);
  priority_queue<Node, vector<Node>, cmp> q;
  q.push( 0);
  dist[0] = 0;
  while (!q.empty())
  {
    Node node = q.top();
    q.pop();
    int id = node.id;
    if (vis[id]) continue;
    vis[id] = true;
    for (int i = 0; i < n; i++)
    {
      if (!vis[i] && graph[id][i] > 0 && graph[id][i] < dist[i])
      {
        dist[i] = graph[id][i];
        q.push({ i, dist[i] });
      }
    }
  }
}

最后，我们需要调用上面的函数，输入图的节点数和邻接矩阵，就能够得到最小生成树的边权值之和。代码如下：


int main()
{
  int n = 5;
  vector<vector<int>> graph = {
     3,
     0,
     0,
     0,
     0
  };
  prim(n, graph);
  return 0;
}

通过上述代码的实现，我们就能够得到最小生成树的边权值之和。在实际的问题中，Prim算法是非常常用的一种算法，可以用于解决许多最优化问题。

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

下一篇: C++Builder生成VC库的方法

评论区

()

相似文章