用c语言写一个邻接表存储连通图，并分别用深度优先和广度优先遍历该连通图

好的，我可以为您提供一个简单的实现。

#include <stdio.h>
#include <stdlib.h>

#define MAX_VERTICES 100

// 邻接表节点结构体
typedef struct AdjListNode {
    int dest;
    struct AdjListNode *next;
} AdjListNode;

// 邻接表结构体
typedef struct AdjList {
    struct AdjListNode *head;
} AdjList;

// 图结构体
typedef struct Graph {
    int num_vertices;
    struct AdjList *array;
} Graph;

// 创建邻接表节点
AdjListNode* createNode(int dest) {
    AdjListNode* newNode = (AdjListNode*)malloc(sizeof(AdjListNode));
    newNode->dest = dest;
    newNode->next = NULL;
    return newNode;
}

// 创建图
Graph* createGraph(int num_vertices) {
    Graph* graph = (Graph*)malloc(sizeof(Graph));
    graph->num_vertices = num_vertices;
    graph->array = (AdjList*)malloc(num_vertices * sizeof(AdjList));
    for (int i = 0; i < num_vertices; ++i) {
        graph->array[i].head = NULL;
    }
    return graph;
}

// 添加边
void addEdge(Graph* graph, int src, int dest) {
    AdjListNode* newNode = createNode(dest);
    newNode->next = graph->array[src].head;
    graph->array[src].head = newNode;

    newNode = createNode(src);
    newNode->next = graph->array[dest].head;
    graph->array[dest].head = newNode;
}

// 深度优先遍历
void DFS(Graph* graph, int vertex, int* visited) {
    visited[vertex] = 1;
    printf("%d ", vertex);

    AdjListNode* temp = graph->array[vertex].head;
    while (temp) {
        int adj_vertex = temp->dest;
        if (!visited[adj_vertex]) {
            DFS(graph, adj_vertex, visited);
        }
        temp = temp->next;
    }
}

// 广度优先遍历
void BFS(Graph* graph, int start_vertex, int* visited) {
    int queue[MAX_VERTICES];
    int front = 0, rear = 0;

    visited[start_vertex] = 1;
    queue[rear++] = start_vertex;

    while (front < rear) {
        int vertex = queue[front++];
        printf("%d ", vertex);

        AdjListNode* temp = graph->array[vertex].head;
        while (temp) {
            int adj_vertex = temp->dest;
            if (!visited[adj_vertex]) {
                visited[adj_vertex] = 1;
                queue[rear++] = adj_vertex;
            }
            temp = temp->next;
        }
    }
}

int main() {
    int num_vertices, num_edges, src, dest;
    printf("Enter the number of vertices: ");
    scanf("%d", &num_vertices);
    Graph* graph = createGraph(num_vertices);
    printf("Enter the number of edges: ");
    scanf("%d", &num_edges);
    for (int i = 0; i < num_edges; ++i) {
        printf("Enter edge %d: ", i + 1);
        scanf("%d%d", &src, &dest);
        addEdge(graph, src, dest);
    }

    int visited[MAX_VERTICES] = {0};

    printf("DFS traversal: ");
    for (int i = 0; i < num_vertices; ++i) {
        if (!visited[i]) {
            DFS(graph, i, visited);
        }
    }

    printf("\nBFS traversal: ");
    for (int i = 0; i < num_vertices; ++i) {
        visited[i] = 0;
    }
    BFS(graph, 0, visited);

    return 0;
}

在这个实现中，我们使用了邻接表来表示图，并使用深度优先遍历和广度优先遍历来遍历图。在创建图时，我们首先创建一个 `Graph` 结构体，该结构体包含了图的顶点数和一个指向邻接表数组的指针。邻接表数组中的每个元素都是一个邻接表，每个邻接表包含一个指向邻接表节点的指针。邻接表节点包含一个目标顶点和一个指向下一个邻接表节点的指针。

在程序中，我们首先要求用户输入图的顶点数和边数。然后，我们使用 `createGraph` 函数创建一个空图，并使用 `addEdge` 函数添加边。在遍历图时，我们使用 `DFS` 和 `BFS` 函数分别进行深度优先遍历和广度优先遍历。在 `DFS` 和 `BFS` 函数中，我们使用一个 `visited` 数组来记录已经访问过的顶点，并保证每个顶点只被访问一次。

希望这个实现可以帮助您理解如何使用邻接表来表示连通图，并使用深度优先遍历和广度优先遍历来遍历图。