C++图论代码 |21xrx.com

C++图论代码

2023-07-06 13:29:18 深夜i -- --

C++编程语言图论算法代码编写图模型计算机科学

C++是一种常用的编程语言，其在图论领域的应用极为广泛。下面就分享一些C++图论代码，帮助大家更加深入理解图论算法。

一、Dijkstra算法

Dijkstra算法用于求解从源点到其它所有节点的最短路径，其实现过程可以通过使用优先队列来实现，具体代码如下：


void Dijkstra(int start) {
  memset(visited, false, sizeof(visited));
  memset(dist, 0x3f, sizeof(dist));
  dist[start] = 0;
  priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > q;
  q.push(make_pair(0, start));
  while (!q.empty()) {
    int u = q.top().second;
    q.pop();
    if (visited[u])
      continue;
    
    visited[u] = true;
    for (int i = 0; i < adj[u].size(); ++i) {
      int v = adj[u][i].first;
      int w = adj[u][i].second;
      if (dist[u] + w < dist[v]) {
        dist[v] = dist[u] + w;
        q.push(make_pair(dist[v], v));
      }
    }
  }
}

二、Prim算法

Prim算法用于求解最小生成树问题，其实现过程也是通过使用优先队列来实现，具体代码如下：


void Prim(int start) {
  memset(visited, false, sizeof(visited));
  memset(dist, 0x3f, sizeof(dist));
  dist[start] = 0;
  priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > q;
  q.push(make_pair(0, start));
  while (!q.empty()) {
    int u = q.top().second;
    q.pop();
    if (visited[u])
      continue;
    
    visited[u] = true;
    for (int i = 0; i < adj[u].size(); ++i) {
      int v = adj[u][i].first;
      int w = adj[u][i].second;
      if (!visited[v] && w < dist[v]) {
        dist[v] = w;
        q.push(make_pair(w, v));
      }
    }
  }
}

三、Floyd算法

Floyd算法用于求解任意两个节点之间的最短路径，其实现过程需要使用动态规划思想，其代码如下：


void Floyd() {
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
      dist[i][j] = adj[i][j];
    }
  }
  for (int k = 1; k <= n; ++k) {
    for (int i = 1; i <= n; ++i) {
      for (int j = 1; j <= n; ++j) {
        if (dist[i][j] > dist[i][k] + dist[k][j]) {
          dist[i][j] = dist[i][k] + dist[k][j];
        }
      }
    }
  }
}

四、拓扑排序算法

拓扑排序算法用于对图进行排序，从而确定图中各个节点的顺序关系，其实现过程需要使用队列来实现，其代码如下：


void Topsort() {
  queue<int> q;
  for (int i = 1; i <= n; ++i) {
    if (indegree[i] == 0) {
      q.push(i);
    }
  }
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    ans.push_back(u);
    for (int i = 0; i < adj[u].size(); ++i) {
      int v = adj[u][i].first;
      indegree[v]--;
      if (indegree[v] == 0) {
        q.push(v);
      }
    }
  }
}

以上就是一些常用的图论算法的代码实现，通过学习这些代码，相信大家对图论算法的理解能够更加深入，进而在实际工作或学习中更加得心应手。

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

下一篇: C++简单界面设计

评论区

()

相似文章