C++深度优先搜索 |holyya.com

C++深度优先搜索

2023-06-27 13:08:44 深夜i -- --

C++ 深度优先搜索算法图论递归

C++是一种广泛使用的编程语言，非常适合进行算法设计与实现。深度优先搜索（DFS）是计算机科学中的重要算法，其用途包括图形处理和路径查找等任务。本文将介绍如何在C++中实现深度优先搜索。

深度优先搜索是一种遍历图中节点的算法，它从一条路径的起始点开始遍历，当无法继续向下搜索时，返回上一个节点并继续搜索其他路径。这个过程会一直持续，直到所有节点都被访问过且每个节点都被遍历过。采用深度优先搜索时，程序会用堆栈来存储已经过的路径信息。

在C++中实现深度优先搜索的过程一般包括以下几步：

1.定义一个数据结构来表示图形，通常使用邻接表或邻接矩阵。

2.定义访问节点的函数。该函数应该检查节点是否已经被访问过，如果没有，则记录该节点已经被访问，并递归访问该图中的相邻节点。在递归访问相邻节点时，需要再次调用该函数。

3.为避免重复访问节点，需要定义一个布尔变量来保存每个节点的访问状态。该变量可以作为参数传递给访问节点的函数。

4.为了支持回溯，需要使用一个堆栈来存储路径信息。需要在每次访问节点时把节点压入堆栈中，并在访问相邻节点时，将其记录到堆栈中。

下面是一个简单的例子，展示了如何在C++中实现深度优先搜索算法。


#include <iostream>
#include <vector>
#include <stack>
using namespace std;
class Graph {
private:
  int nodes;
  vector< vector<int> > adjacencyList;
public:
  Graph(int nodes) {
   this->nodes = nodes;
   this->adjacencyList.resize(nodes);
  }
  void addEdge(int u, int v) {
   this->adjacencyList[u].push_back(v);
   this->adjacencyList[v].push_back(u);
   return;
  }
  void dfs(int start) {
   vector<bool> visited(this->nodes, false);
   stack<int> path;
   path.push(start);
   while(!path.empty()) {
     int currentNode = path.top();
     path.pop();
     if(!visited[currentNode]) {
      visited[currentNode] = true;
      cout << currentNode << " ";
      for(int i = 0; i < this->adjacencyList[currentNode].size(); i++) {
        int vertex = this->adjacencyList[currentNode][i];
        if(!visited[vertex]) {
         path.push(vertex);
        }
      }
     }
   }
  }
};
int main() {
  Graph graph(6);
  graph.addEdge(0, 1);
  graph.addEdge(0, 2);
  graph.addEdge(1, 2);
  graph.addEdge(1, 4);
  graph.addEdge(1, 3);
  graph.addEdge(2, 3);
  graph.addEdge(3, 5);
  cout << "DFS traversal starting from vertex 0: ";
  graph.dfs(0);
  cout << endl;
  return 0;
}

在上面的代码中，我们首先定义了一个Graph类来表示图形，并定义addEdge函数来添加边。接下来，定义了dfs函数来执行深度优先搜索。dfs函数使用了一个布尔数组visited来记录节点的访问状态，一个栈path来存储所有已访问节点的路径信息。我们使用while循环来遍历所有未访问节点，如果该节点未被访问过，则将其标记为已访问，并把其值添加到输出中，接下来遍历其所有未访问的相邻节点，并将其压入堆栈中。

在main函数中，我们添加了一个6个节点的图形，然后调用dfs函数来执行深度优先搜索，并以0为第一个节点开始。输出应该为：“DFS traversal starting from vertex 0: 0 2 3 5 1 4”。

In conclusion, C++ is a powerful programming language that can be used to implement complex algorithms like Depth First Search. With the correct use of data structures and the recursive search function, it is easy to implement this algorithm in C++. Depth First Search is a very useful algorithm for tackling a variety of problems and can be applied to many different scenarios.

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

下一篇: C++中main函数的返回值

评论区

()

相似文章