C++邻接表路径的遍历

在图论中，邻接表是一种常用的数据结构，用于存储图中的节点和它们之间的连接。对于路径遍历，特别是在有向或无向图中寻找从一个节点到另一个节点的路径，我们可以使用深度优先搜索（DFS）或广度优先搜索（BFS）。

**深度优先搜索（DFS）：**
DFS 适合于发现是否存在路径，它通常从起点开始，沿着一条边走到底，直到无法继续为止，然后回溯到上一个节点并尝试其他分支。在邻接列表中，可以使用递归或栈来实现：

void dfs(int node, vector<vector<int>>& adjList, vector<bool>& visited) {
    visited[node] = true;
    cout << node << " ";
    for (int neighbor : adjList[node]) {
        if (!visited[neighbor])
            dfs(neighbor, adjList, visited);
    }
}

调用 `dfs(startNode, adjList, visited)`。

**广度优先搜索（BFS）：**
BFS 更适合找出两个节点间的最短路径，因为它总是先访问最近的未访问节点。在邻接列表中，可以使用队列来实现：

void bfs(int startNode, vector<vector<int>>& adjList) {
    queue<int> q;
    vector<bool> visited(adjList.size(), false);
    visited[startNode] = true;
    q.push(startNode);

    while (!q.empty()) {
        int current = q.front();
        cout << current << " ";
        q.pop();

        for (int neighbor : adjList[current]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                q.push(neighbor);
            }
        }
    }
}

调用 `bfs(startNode, adjList)`。

**相关问题--:**
1. 邻接表数据结构是如何表示图的？
2. 何时使用 DFS 进行路径遍历？
3. BFS 和 DFS 的区别是什么？
4. 如何根据实际需求选择 DFS 或 BFS？