4.采用邻接表表示,实现无向图的深度优先搜索遍历。用C++完整

使用邻接表表示的无向图进行深度优先搜索（DFS）遍历，可以利用队列数据结构来保存待访问的节点。以下是C++语言的一个简单示例：

#include <iostream>
#include <vector>
using namespace std;

// 定义图的邻接表结构
class Graph {
private:
    vector<vector<int>> adj; // 存储邻接点的列表

public:
    void addEdge(int src, int dest) {
        adj[src].push_back(dest); // 添加边到源节点的列表
        adj[dest].push_back(src); // 添加反向边到目的节点的列表（因为图是无向的）
    }

    void dfs(int start) {
        vector<bool> visited(adj.size(), false); // 记录每个节点是否被访问过
        vector<int> stack; // 遍历使用的栈

        visited[start] = true;
        stack.push_back(start);

        while (!stack.empty()) {
            int curr = stack.back(); // 取出栈顶节点
            cout << curr << " "; // 输出当前节点
            stack.pop_back();

            for (int neighbor : adj[curr]) { // 遍历邻居节点
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    stack.push_back(neighbor);
                }
            }
        }
    }
};

int main() {
    Graph g;
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 2);
    g.addEdge(2, 0);

    cout << "Depth First Search Traversal (starting from node 2): ";
    g.dfs(2);
    return 0;
}

在这个例子中，我们首先创建一个`Graph`类，其中包含一个邻接表`adj`。然后定义了添加边`addEdge`和深度优先搜索`dfs`函数。`dfs`函数会从给定的起始节点开始，访问并标记所有可达的节点，直到遍历完整个路径。

运行这个程序时，从节点2开始的深度优先搜索将输出：`2 0 1 2`（根据无向图的特点，起点到终点有两条路径）。