C++图的深度和广度遍历 |21xrx.com

C++图的深度和广度遍历

2023-07-13 03:33:31 深夜i -- --

C++ 图深度遍历广度遍历

C++是一种使用广泛的编程语言，它支持许多数据结构和算法。其中，图是一种非常有用的数据结构，可以用来表示和解决许多实际问题。在图的算法中，深度优先搜索和广度优先搜索是两种非常常用的算法，本文将介绍如何在C++中实现它们。

深度优先搜索（DFS）是一种用于遍历图的算法。它从某个节点开始，依次访问它的相邻节点，直到访问到没有未访问节点的节点为止。我们可以通过使用递归或栈来实现DFS。下面是一个使用递归实现DFS的C++代码：


void DFS(int v, vector<bool>& visited, vector<vector<int>>& graph) {
  visited[v] = true;
  // 在这里处理节点v
  for (int i = 0; i < graph[v].size(); ++i) {
    int u = graph[v][i];
    if (!visited[u]) {
      DFS(u, visited, graph);
    }
  }
}

其中，v表示当前要遍历的节点，visited表示每个节点的访问情况，graph表示图的邻接矩阵。当访问到某个节点时，我们将visited的相应位置标记为true，并遍历它的所有相邻节点（即graph[v]表示v的所有邻居），如果它的邻居节点没有被访问过，则继续递归地访问它。

广度优先搜索（BFS）是一种从图的某个节点开始遍历所有节点的算法。与DFS类似，BFS也需要一个队列来保存待遍历的节点。BFS从起始节点开始，将其加入队列，然后对队列中的节点进行出队操作，访问其相邻节点，并将其加入队列中。下面是一个使用队列实现BFS的C++代码：


void BFS(int v, vector<bool>& visited, vector<vector<int>>& graph) {
  queue<int> q;
  q.push(v);
  visited[v] = true;
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    // 在这里处理节点u
    for (int i = 0; i < graph[u].size(); ++i) {
      int w = graph[u][i];
      if (!visited[w]) {
        visited[w] = true;
        q.push(w);
      }
    }
  }
}

其中，v表示起始节点，visited表示每个节点的访问情况，graph表示图的邻接矩阵。我们首先将起始节点v加入队列中，并将visited的相应位置标记为true。然后，当队列不为空时，我们对队列中的节点进行出队操作，访问其相邻节点并将其加入队列中，直到队列为空。在访问每个节点之前，我们需要检查它是否已经被访问过，以避免无限循环。

需要注意的是，在使用DFS和BFS遍历图时，我们需要对每个节点进行一些处理，例如打印节点的值或更新它们的状态。此外，我们还可以使用DFS或BFS来找到图中的路径，或者进行其他诸如拓扑排序等操作。

总之，C++提供了许多图算法和数据结构的实现，如深度优先搜索和广度优先搜索。使用这些算法和数据结构可以轻松地解决许多实际问题。如果您想深入了解图和其他算法，请查阅相关文献。

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

下一篇: C++社招面试知识点总结

评论区

()

相似文章