c++深度优先搜索与广度优先搜索 |21xrx.com

c++深度优先搜索与广度优先搜索

2023-07-01 10:19:54 深夜i -- --

C++ 深度优先搜索广度优先搜索图算法搜索算法

C++深度优先搜索与广度优先搜索

在计算机科学中，深度优先搜索（DFS）和广度优先搜索（BFS）是两种常用的图搜索算法。它们在解决不同类型的问题时具有不同的优势和适用性。这两种算法在C++中是非常强大和常用的。

深度优先搜索是一种递归的搜索策略，它通过探索尽可能深的节点。该算法从起始节点开始，逐个遍历其相邻节点，并沿着每个未访问节点的路径一直到达尽可能深的节点，然后回溯到上一个节点并继续搜索。这个过程一直进行，直到找到目标节点或遍历完整个图。

广度优先搜索是一种迭代的搜索策略，它从起始节点开始，首先遍历其所有相邻节点，然后继续遍历这些相邻节点的相邻节点，直到找到目标节点或遍历完整个图。这种搜索策略在搜索最短路径或找到最近的节点时非常有用。

在C++中，可以使用图的邻接列表或邻接矩阵来表示图，并使用深度优先搜索和广度优先搜索算法进行遍历和搜索。以下是一个使用邻接列表表示图并进行深度优先搜索的示例代码：


#include<iostream>
#include<vector>
#include<stack>
using namespace std;
void DFS(vector<vector<int>>& graph, int start, vector<bool>& visited) {
  stack<int> s;
  s.push(start);
  visited[start] = true;
  while (!s.empty()) {
    int curr = s.top();
    s.pop();
    cout << curr << " ";
    for (int neighbor : graph[curr]) {
      if (!visited[neighbor]) {
        s.push(neighbor);
        visited[neighbor] = true;
      }
    }
  }
}
int main() {
  int n; // 节点数
  int m; // 边数
  cin >> n >> m;
  vector<vector<int>> graph(n);
  for (int i = 0; i < m; i++) {
    int u, v;
    cin >> u >> v;
    graph[u].push_back(v);
    graph[v].push_back(u);
  }
  int start; // 起始节点
  cin >> start;
  vector<bool> visited(n, false);
  cout << "深度优先搜索结果：";
  DFS(graph, start, visited);
  return 0;
}

上面的代码中，我们首先定义了一个用于深度优先搜索的函数DFS。在DFS函数中，使用了一个堆栈数据结构来存储需要继续遍历的节点。我们从起始节点开始，通过将其入栈并将其标记为已访问来开始遍历。然后，我们进入一个循环，直到堆栈为空。在每次循环迭代中，我们从堆栈中取出当前节点并输出它，然后遍历其所有未访问的相邻节点，并将它们入栈并标记为已访问。这个过程一直进行，直到完成整个深度优先搜索。

类似地，我们还可以使用类似的方法来实现广度优先搜索。以下是一个使用队列来实现广度优先搜索的示例代码：


#include<iostream>
#include<vector>
#include<queue>
using namespace std;
void BFS(vector<vector<int>>& graph, int start, vector<bool>& visited) {
  queue<int> q;
  q.push(start);
  visited[start] = true;
  while (!q.empty()) {
    int curr = q.front();
    q.pop();
    cout << curr << " ";
    for (int neighbor : graph[curr]) {
      if (!visited[neighbor]) {
        q.push(neighbor);
        visited[neighbor] = true;
      }
    }
  }
}
int main() {
  int n; // 节点数
  int m; // 边数
  cin >> n >> m;
  vector<vector<int>> graph(n);
  for (int i = 0; i < m; i++) {
    int u, v;
    cin >> u >> v;
    graph[u].push_back(v);
    graph[v].push_back(u);
  }
  int start; // 起始节点
  cin >> start;
  vector<bool> visited(n, false);
  cout << "广度优先搜索结果：";
  BFS(graph, start, visited);
  return 0;
}

在上面的代码中，我们定义了一个用于广度优先搜索的函数BFS。在BFS函数中，我们使用了一个队列来存储需要继续遍历的节点。我们从起始节点开始，并通过将其入队列并标记为已访问来开始遍历。然后，我们进入一个循环，直到队列为空。在每次循环迭代中，我们从队列中取出当前节点并输出它，然后遍历其所有未访问的相邻节点，并将它们入队列并标记为已访问。这个过程一直进行，直到完成整个广度优先搜索。

综上所述，C++中的深度优先搜索和广度优先搜索算法是非常强大和常用的。它们可以用于解决各种问题，如查找最短路径，遍历图以及找到与某个节点相关的所有节点等。通过理解和应用这些算法，我们可以更好地理解和处理图数据结构。

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

下一篇: Node.js中哪些变量可用于全局访问数据库？

评论区

()

相似文章