用c语言输入无向图的顶点数、边数及各条边的顶点对，建立用邻接表表示的无向图，对图进行深度优先搜索和广度优先搜索遍历，并分别输出其遍历序列。及空间复杂度和时间复杂度

下面是用C语言实现建立邻接表表示的无向图、深度优先搜索和广度优先搜索遍历的代码。

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

// 定义邻接表结构体
typedef struct Node {
    int adjvex; // 邻接点下标
    struct Node *next; // 指向下一个邻接点的指针
}Node;

// 定义顶点结构体
typedef struct {
    int data; // 顶点数据
    Node *first; // 邻接点链表头指针
}Vertex;

// 定义图结构体
typedef struct {
    Vertex *vexs; // 存储所有顶点的数组
    int vexnum; // 顶点数
    int edgenum; // 边数
}Graph;

// 初始化邻接表
void init(Vertex *vexs, int n) {
    for (int i = 0; i < n; i++) {
        vexs[i].data = i + 1; // 顶点数据为1~n
        vexs[i].first = NULL; // 邻接点链表头指针初始化为NULL
    }
}

// 添加边
void addEdge(Vertex *vexs, int i, int j) {
    Node *p = vexs[i].first;
    Node *newNode = (Node *)malloc(sizeof(Node)); // 创建新的邻接点节点
    newNode->adjvex = j; // 设置邻接点下标
    newNode->next = NULL;
    if (p == NULL) {
        vexs[i].first = newNode; // 如果链表为空，将新节点设为链表头
    }
    else {
        while (p->next != NULL) {
            p = p->next; // 找到链表末尾
        }
        p->next = newNode; // 将新节点插入链表末尾
    }
}

// 深度优先搜索遍历
void DFS(Graph *g, int i, int *visited, int *result) {
    visited[i] = 1; // 标记当前节点已经被访问过
    result[i] = g->vexs[i].data; // 记录遍历序列
    Node *p = g->vexs[i].first;
    while (p != NULL) {
        if (visited[p->adjvex] == 0) { // 如果当前邻接点未被访问过，则递归访问它
            DFS(g, p->adjvex, visited, result);
        }
        p = p->next;
    }
}

// 广度优先搜索遍历
void BFS(Graph *g, int i, int *visited, int *result) {
    int queue[g->vexnum]; // 定义队列
    int front = 0, rear = 0;
    visited[i] = 1; // 标记当前节点已经被访问过
    result[rear++] = g->vexs[i].data; // 记录遍历序列
    queue[rear++] = i; // 将当前节点入队
    while (front < rear) {
        int j = queue[front++]; // 取出队头节点
        Node *p = g->vexs[j].first;
        while (p != NULL) {
            if (visited[p->adjvex] == 0) { // 如果当前邻接点未被访问过，则标记已访问并入队
                visited[p->adjvex] = 1;
                result[rear++] = g->vexs[p->adjvex].data;
                queue[rear++] = p->adjvex;
            }
            p = p->next;
        }
    }
}

int main() {
    int n, m;
    printf("请输入无向图的顶点数：");
    scanf("%d", &n);
    printf("请输入无向图的边数：");
    scanf("%d", &m);

    Graph g;
    g.vexnum = n;
    g.edgenum = m;
    g.vexs = (Vertex *)malloc(sizeof(Vertex) * n); // 创建存储所有顶点的数组
    init(g.vexs, n); // 初始化邻接表

    // 读入所有边并添加到邻接表
    for (int i = 0; i < m; i++) {
        int u, v;
        printf("请输入第%d条边的两个顶点下标：", i + 1);
        scanf("%d%d", &u, &v);
        addEdge(g.vexs, u - 1, v - 1);
        addEdge(g.vexs, v - 1, u - 1);
    }

    // 深度优先搜索遍历
    int *visited = (int *)malloc(sizeof(int) * n);
    int *result1 = (int *)malloc(sizeof(int) * n);
    for (int i = 0; i < n; i++) {
        visited[i] = 0; // 初始化所有节点未被访问过
    }
    printf("深度优先搜索遍历序列：");
    for (int i = 0; i < n; i++) {
        if (visited[i] == 0) { // 如果当前节点未被访问过，则从该节点开始进行深度优先搜索
            DFS(&g, i, visited, result1);
        }
    }
    for (int i = 0; i < n; i++) {
        printf("%d ", result1[i]);
    }
    printf("\n");

    // 广度优先搜索遍历
    int *result2 = (int *)malloc(sizeof(int) * n);
    for (int i = 0; i < n; i++) {
        visited[i] = 0; // 初始化所有节点未被访问过
    }
    printf("广度优先搜索遍历序列：");
    for (int i = 0; i < n; i++) {
        if (visited[i] == 0) { // 如果当前节点未被访问过，则从该节点开始进行广度优先搜索
            BFS(&g, i, visited, result2);
        }
    }
    for (int i = 0; i < n; i++) {
        printf("%d ", result2[i]);
    }
    printf("\n");

    free(g.vexs);
    free(visited);
    free(result1);
    free(result2);

    return 0;
}

时间复杂度：

- 建立邻接表：O(m)
- 深度优先搜索遍历：O(n+m)
- 广度优先搜索遍历：O(n+m)

空间复杂度：O(n+m)