C++对图中路径的遍历

在C++中，图的遍历主要有两种主要方法：深度优先搜索(DFS)和广度优先搜索(BFS)。这两种算法在处理路径问题时非常有用。

**1. 深度优先搜索（DFS）**
- DFS从图中的任意节点开始，沿着一条未访问过的边深入搜索直到到达最深的分支，然后回溯到上一层，重复这个过程直到所有可达节点都被访问过。
- 常用的数据结构是栈（递归实现）或堆（非递归实现），用于跟踪待访问的节点和路径。
- 示例代码（使用栈）：

   void dfs(vector<vector<int>>& graph, int start, vector<bool>& visited, vector<int>& path) {
       visited[start] = true;
       path.push_back(start);
       for (int neighbor : graph[start]) {
           if (!visited[neighbor]) {
               dfs(graph, neighbor, visited, path);
           }
       }
       // 当遍历完子树后，回溯
       path.pop_back();
   }

**2. 广度优先搜索（BFS）**
- BFS是从起点开始，逐层扩展节点，先访问距离起点近的节点再访问远的节点。
- 常用的数据结构是队列，因为BFS总是按照先进先出(FIFO)顺序进行的。
- 示例代码（使用队列）：

   void bfs(vector<vector<int>>& graph, int start, vector<int>& result) {
       queue<int> q;
       vector<bool> visited(graph.size(), false);
       q.push(start);
       visited[start] = true;
       while (!q.empty()) {
           int current = q.front(); q.pop();
           result.push_back(current);
           for (int neighbor : graph[current]) {
               if (!visited[neighbor]) {
                   q.push(neighbor);
                   visited[neighbor] = true;
               }
           }
       }
   }

这里`graph`是一个邻接列表表示的图，`start`是起始点，`visited`用来标记已访问过的节点，`path`或`result`记录路径。

如果你想找到两个节点之间的最短路径，BFS通常更适用，因为它是寻找最短路径的标准算法。如果需要找到所有的路径，DFS可能更适合。