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

在C++中，使用邻接表来表示无向图非常适合深度优先搜索（DFS）。邻接表是一种常见的图数据结构，它将每个顶点关联到其相邻的所有顶点列表。以下是使用邻接表实现无向图DFS的基本步骤：

#include <iostream>
#include <vector>

// 图节点定义
struct Node {
    int data; // 节点数据
    std::vector<Node*> neighbors; // 邻居列表
};

// 深度优先搜索函数
void dfs(Node* start, bool visited[]) {
    if (visited[start->data]) return; // 如果已经访问过，跳过
    visited[start->data] = true; // 标记当前节点已访问

    std::cout << start->data << " "; // 输出节点值
    for (Node* neighbor : start->neighbors) {
        dfs(neighbor, visited); // 对未访问过的邻居递归调用dfs
    }
}

int main() {
    // 创建示例无向图并设置邻接表
    Node nodes[] = { ... }; // 初始化节点数组，包含数据和邻接节点指针
    Node* graph[节点总数]; // 存储邻接表，初始化为NULL
    for (int i = 0; i < 节点总数; ++i) {
        graph[i] = &nodes[i];
        // 添加边，这里假设nodes[i].neighbors直接存储了邻接节点的索引
    }

    // 开始深度优先搜索
    bool visited[节点总数] = {false}; // 初始化所有节点为未访问
    dfs(graph[起点索引], visited);

    return 0;
}

在这个例子中，`dfs`函数从给定的起始节点开始，标记每个访问过的节点，并对未访问的邻居递归地调用自身。`main`函数里创建了图的数据结构并调用`dfs`来进行遍历。