用邻接表作为图的存储结构建立一个图，并对此图分别进行深度优先搜索和广度优先搜索遍历。（c语言实现）

好的，下面是使用邻接表作为图的存储结构，并对图进行深度优先搜索和广度优先搜索遍历的 C 语言实现示例。

首先，我们需要定义一个邻接表结构体，用来表示图的节点和边。该结构体包含两个成员变量：一个指向节点的指针和一个整型值（表示节点的编号）。节点结构体中还包含一个指向链表的指针，链表中记录了该节点所连接的其他节点。

// 邻接表节点
struct adj_list_node {
    int dest;  // 目标节点编号
    struct adj_list_node* next;  // 指向下一个节点的指针
};

// 邻接表头节点
struct adj_list_head {
    struct adj_list_node* head;  // 指向链表头的指针
};

// 图结构体
struct graph {
    int num_vertices;  // 节点数
    struct adj_list_head* array;  // 邻接表数组
};

接下来，我们需要实现一个函数来创建并初始化一个新的图。该函数需要为图结构体和邻接表节点动态分配内存，并将它们初始化为默认值。

// 创建一个新的图
struct graph* create_graph(int num_vertices) {
    struct graph* g = (struct graph*)malloc(sizeof(struct graph));
    g->num_vertices = num_vertices;
    g->array = (struct adj_list_head*)malloc(num_vertices * sizeof(struct adj_list_head));
    for (int i = 0; i < num_vertices; i++) {
        g->array[i].head = NULL;
    }
    return g;
}

接下来，我们需要实现一个函数来添加一条边到图中。该函数需要将边的起始节点和目标节点添加到邻接表中。

// 添加一条边到图中
void add_edge(struct graph* g, int src, int dest) {
    // 添加从源节点到目标节点的边
    struct adj_list_node* new_node = (struct adj_list_node*)malloc(sizeof(struct adj_list_node));
    new_node->dest = dest;
    new_node->next = g->array[src].head;
    g->array[src].head = new_node;

    // 添加从目标节点到源节点的边（因为是无向图）
    new_node = (struct adj_list_node*)malloc(sizeof(struct adj_list_node));
    new_node->dest = src;
    new_node->next = g->array[dest].head;
    g->array[dest].head = new_node;
}

现在，我们可以用上面的函数来创建一个新的图，并添加一些边：

int main() {
    struct graph* g = create_graph(6);
    add_edge(g, 0, 1);
    add_edge(g, 0, 2);
    add_edge(g, 1, 2);
    add_edge(g, 1, 3);
    add_edge(g, 2, 3);
    add_edge(g, 2, 4);
    add_edge(g, 3, 4);
    add_edge(g, 3, 5);
    return 0;
}

现在，我们可以实现深度优先搜索和广度优先搜索算法，对这个图进行遍历。下面是深度优先搜索的 C 语言实现：

// 深度优先搜索
void dfs(struct graph* g, int vertex, int* visited) {
    visited[vertex] = 1;
    printf("%d ", vertex);

    struct adj_list_node* node = g->array[vertex].head;
    while (node != NULL) {
        int dest = node->dest;
        if (!visited[dest]) {
            dfs(g, dest, visited);
        }
        node = node->next;
    }
}

该函数使用一个数组来记录已经访问过的节点，遍历每个节点，并递归遍历它的邻居节点。下面是广度优先搜索的 C 语言实现：

// 广度优先搜索
void bfs(struct graph* g, int start) {
    int visited[g->num_vertices];
    memset(visited, 0, sizeof(visited));

    visited[start] = 1;
    printf("%d ", start);

    queue<int> q;
    q.push(start);

    while (!q.empty()) {
        int vertex = q.front();
        q.pop();

        struct adj_list_node* node = g->array[vertex].head;
        while (node != NULL) {
            int dest = node->dest;
            if (!visited[dest]) {
                visited[dest] = 1;
                printf("%d ", dest);
                q.push(dest);
            }
            node = node->next;
        }
    }
}

该函数使用一个队列来存储要访问的节点，遍历每个节点，并将它的邻居节点加入队列中。下面是遍历这个图的示例代码：

int main() {
    struct graph* g = create_graph(6);
    add_edge(g, 0, 1);
    add_edge(g, 0, 2);
    add_edge(g, 1, 2);
    add_edge(g, 1, 3);
    add_edge(g, 2, 3);
    add_edge(g, 2, 4);
    add_edge(g, 3, 4);
    add_edge(g, 3, 5);

    int visited[g->num_vertices];
    memset(visited, 0, sizeof(visited));

    printf("DFS: ");
    dfs(g, 0, visited);
    printf("\n");

    printf("BFS: ");
    bfs(g, 0);
    printf("\n");

    return 0;
}

这个程序将输出深度优先搜索和广度优先搜索的遍历结果。