用C语言编写邻接表实现广度和深度优先搜索

在C语言中，邻接表是一种常见的图数据结构，用于存储无向图或有向图。对于广度优先搜索（BFS，也叫层次遍历），你可以创建一个队列来按照节点间的连接顺序逐层探索图。以下是基本步骤：

1. 初始化：
- 创建一个队列，用于存放待访问的节点。
- 创建一个布尔型数组或哈希表表示每个节点是否被访问过。

2. 开始BFS过程：
- 将起始节点入队。
- 当队列非空时，循环执行以下操作：
a. 出队当前节点。
b. 标记该节点已访问。
c. 遍历与当前节点相邻的所有未访问节点，将它们入队。

3. 深度优先搜索（DFS）则相反，通常使用递归或栈来实现：
- 定义一个函数，接收一个节点作为参数。
- 入栈初始节点，并开始迭代：
a. 如果当前节点未访问，则标记并处理它。
b. 探索当前节点的所有邻居（通过邻接表），对每个未访问邻居递归调用函数。

typedef struct Node {
    int value;
    struct Node* next; // 邻接列表中的下一个节点
} Node;

// 使用邻接表表示图的结构体
typedef struct Graph {
    Node** adj_list; // 用于存储邻接表
    int size;
    // 其他辅助变量...
} Graph;

// BFS和DFS函数示例
void bfs(Graph* graph, int start) {
    Queue* queue = create_queue(); // 初始化队列
    enqueue(queue, &graph->adj_list[start]); // 添加起点到队列
    while (!is_empty(queue)) {
        Node* current = dequeue(queue);
        process_node(current); // 处理节点
        for (Node* neighbor : current->next) {
            if (!visited[neighbor->value]) { // 未访问的邻居
                enqueue(queue, neighbor);
            }
        }
    }
}

void dfs(Graph* graph, int start) {
    stack_push(&stack, &graph->adj_list[start]);
    while (!is_empty(stack)) {
        Node* current = stack_pop(stack);
        process_node(current);
        for (Node* neighbor : current->next) {
            if (!visited[neighbor->value]) { // 未访问的邻居
                stack_push(&stack, neighbor);
            }
        }
    }
}