C语言【问题描述】 设无向图G有n个顶点（设顶点值用1～n编号），m条边。 编写程序，实现以下功能： （1）创建图的邻接表存储结构（存储邻接表时，按给定的边的顺序依次生成边结点，将新生成的边结点插入在链表的头部） （2）深度优先遍历 （3）广度优先遍历 【输入形式】 顶点数目：n 边的条数：m 边的顶点对： （a,b）…… 【输出形式】 深度优先遍历结果 广度优先遍历结果 【样例输入】 5 4 1 2 1 3 2 4 3 5 【样例输出】 1 3 5 2 4 1 3 2 5 4

以下是C语言的代码实现：

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

#define MAX_VERTEX_NUM 100 // 最大顶点数

int visited[MAX_VERTEX_NUM]; // 记录顶点是否被访问过

typedef struct ArcNode {
    int adjvex; // 邻接点的位置
    struct ArcNode *nextarc; // 指向下一条边的指针
} ArcNode;

typedef struct VNode {
    int data; // 顶点信息
    ArcNode *firstarc; // 指向第一条依附该顶点的边的指针
} VNode, AdjList[MAX_VERTEX_NUM];

typedef struct {
    AdjList vertices; // 邻接表
    int vexnum, arcnum; // 图的当前顶点数和边数
} ALGraph;

void CreateGraph(ALGraph *G) {
    int i, j, k;
    ArcNode *e;
    printf("请输入顶点数和边数：\n");
    scanf("%d %d", &(G->vexnum), &(G->arcnum));
    printf("请输入顶点信息：\n");
    for (i = 0; i < G->vexnum; i++) {
        scanf("%d", &(G->vertices[i].data));
        G->vertices[i].firstarc = NULL; // 初始化边表头指针
    }
    printf("请输入边的顶点对：\n");
    for (k = 0; k < G->arcnum; k++) {
        scanf("%d %d", &i, &j);
        e = (ArcNode*)malloc(sizeof(ArcNode));
        e->adjvex = j-1;
        e->nextarc = G->vertices[i-1].firstarc; // 插入到表头
        G->vertices[i-1].firstarc = e;
        e = (ArcNode*)malloc(sizeof(ArcNode));
        e->adjvex = i-1;
        e->nextarc = G->vertices[j-1].firstarc; // 插入到表头
        G->vertices[j-1].firstarc = e;
    }
}

void DFS(ALGraph G, int v) {
    ArcNode *p;
    visited[v] = 1; // 标记为已被访问
    printf("%d ", G.vertices[v].data);
    for (p = G.vertices[v].firstarc; p; p = p->nextarc) {
        if (!visited[p->adjvex]) {
            DFS(G, p->adjvex);
        }
    }
}

void DFSTraverse(ALGraph G) {
    int i;
    for (i = 0; i < G.vexnum; i++) {
        visited[i] = 0; // 初始化所有顶点为未被访问
    }
    printf("深度优先遍历结果：");
    for (i = 0; i < G.vexnum; i++) {
        if (!visited[i]) {
            DFS(G, i);
        }
    }
    printf("\n");
}

void BFSTraverse(ALGraph G) {
    int i, v, front = 0, rear = 0;
    int queue[MAX_VERTEX_NUM]; // 队列
    ArcNode *p;
    for (i = 0; i < G.vexnum; i++) {
        visited[i] = 0; // 初始化所有顶点为未被访问
    }
    printf("广度优先遍历结果：");
    for (i = 0; i < G.vexnum; i++) {
        if (!visited[i]) {
            visited[i] = 1; // 标记为已被访问
            printf("%d ", G.vertices[i].data);
            queue[rear++] = i; // 入队
            while (front != rear) {
                v = queue[front++]; // 出队
                for (p = G.vertices[v].firstarc; p; p = p->nextarc) {
                    if (!visited[p->adjvex]) {
                        visited[p->adjvex] = 1; // 标记为已被访问
                        printf("%d ", G.vertices[p->adjvex].data);
                        queue[rear++] = p->adjvex; // 入队
                    }
                }
            }
        }
    }
    printf("\n");
}

int main() {
    ALGraph G;
    CreateGraph(&G);
    DFSTraverse(G);
    BFSTraverse(G);
    return 0;
}

其中，DFS函数实现深度优先遍历，BFSTraverse函数实现广度优先遍历。CreateGraph函数用于创建图的邻接表存储结构。