21xrx.com
2024-11-05 04:58:58 Tuesday
登录
文章检索 我的文章 写文章
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++中的深度优先搜索和广度优先搜索算法是非常强大和常用的。它们可以用于解决各种问题,如查找最短路径,遍历图以及找到与某个节点相关的所有节点等。通过理解和应用这些算法,我们可以更好地理解和处理图数据结构。

  
  

评论区

{{item['qq_nickname']}}
()
回复
回复