C++ 图的遍历代码 |21xrx.com

C++ 图的遍历代码

2023-07-13 03:49:52 深夜i -- --

C++ 图遍历代码

C++是一种强大的编程语言，它能够实现各种算法和数据结构。其中，图的遍历算法被广泛应用于计算机科学和工程领域中。本篇文章将分享几个有效的C++图的遍历代码，帮助读者更好地掌握图的遍历算法。

代码一：深度优先搜索（DFS）

深度优先搜索（DFS）是一种常见的图遍历算法，它完全探索一个子树之后才回溯到根节点。下面是一个典型的DFS代码：


void dfs(int v) {
  visited[v] = true;
  for (int i : adj[v]) {
    if (!visited[i]) {
      dfs(i);
    }
  }
}

以上代码使用递归方法实现DFS，visited数组用于记录节点是否已经遍历过。当我们访问一个新节点时，将visited标记为true，并遍历它的所有邻居。

代码二：广度优先搜索（BFS）

广度优先搜索（BFS）是另一种常见的图遍历算法，它从距离原点最近的邻居开始遍历。BFS在某些场景下比DFS更有效。下面是一个典型的BFS代码：


void bfs(int s) {
  queue<int> q;
  q.push(s);
  visited[s] = true;
  while (!q.empty()) {
    int v = q.front();
    q.pop();
    for (int i : adj[v]) {
      if (!visited[i]) {
        visited[i] = true;
        q.push(i);
      }
    }
  }
}

以上代码使用队列实现BFS，首先将起点加入队列中，然后遍历它的邻居。当我们遍历到一个新节点时，将visited标记为true，并将该节点加入队列尾部，直到队列为空为止。

代码三：拓扑排序

拓扑排序是图的一种有向无环图（DAG）的排序算法。它根据图中的依赖关系对节点进行排序。下面是一个典型的拓扑排序代码：


void toposort() {
  vector<int> indegrees(n, 0);
  for (int i = 0; i < n; i++) {
    for (int j : adj[i]) {
      indegrees[j]++;
    }
  }
  queue<int> q;
  for (int i = 0; i < n; i++) {
    if (indegrees[i] == 0) {
      q.push(i);
    }
  }
  while (!q.empty()) {
    int v = q.front();
    q.pop();
    for (int i : adj[v]) {
      indegrees[i]--;
      if (indegrees[i] == 0) {
        q.push(i);
      }
    }
    // print v
  }
}

以上代码使用队列实现拓扑排序，首先计算每个节点的入度。然后将入度为0的节点加入队列中，并依次弹出队列中的节点，并更新它们的邻居节点的入度。最后输出它们弹出的节点，就得到了一个拓扑排序的结果。

以上是几个常见的C++图的遍历算法代码，它们都有很高的效率和实用性。读者可以根据自己的需要和场景选择不同的算法。最好的方法是将它们应用于实际问题中，以更好地理解这些算法。

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

下一篇: 程序运行过程？

评论区

()

相似文章