邻接表存储结构创建图，掌握图的深度优先遍历和广度优先遍历c语言代码

邻接表存储结构创建图的代码：

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

#define MAX_VERTEX_NUM 20 // 最大顶点数

// 邻接表中的边结构体
typedef struct ArcNode {
    int adjvex; // 该边所指向的顶点的位置
    struct ArcNode *next; // 指向下一条边的指针
} ArcNode;

// 邻接表中的顶点结构体
typedef struct VNode {
    char data; // 顶点的数据域
    ArcNode *firstarc; // 指向第一条依附该顶点的边的指针
} VNode, AdjList[MAX_VERTEX_NUM];

// 图结构体
typedef struct {
    AdjList vertices; // 邻接表
    int vexnum; // 顶点数
    int arcnum; // 边数
} ALGraph;

// 创建图
void CreateGraph(ALGraph *G) {
    printf("请输入顶点数和边数：");
    scanf("%d %d", &G->vexnum, &G->arcnum);
    getchar();

    printf("请输入%d个顶点：", G->vexnum);
    for (int i = 0; i < G->vexnum; i++) {
        scanf("%c", &G->vertices[i].data);
        G->vertices[i].firstarc = NULL;
    }
    getchar();

    printf("请输入%d条边，并指定它们的两个端点，如：0 1\n", G->arcnum);
    for (int i = 0; i < G->arcnum; i++) {
        int v1, v2;
        scanf("%d %d", &v1, &v2);
        getchar();

        ArcNode *arc1 = (ArcNode *)malloc(sizeof(ArcNode));
        arc1->adjvex = v2;
        arc1->next = G->vertices[v1].firstarc;
        G->vertices[v1].firstarc = arc1;

        ArcNode *arc2 = (ArcNode *)malloc(sizeof(ArcNode));
        arc2->adjvex = v1;
        arc2->next = G->vertices[v2].firstarc;
        G->vertices[v2].firstarc = arc2;
    }
}

// 深度优先遍历
void DFS(ALGraph G, int v, int visited[]) {
    visited[v] = 1;
    printf("%c ", G.vertices[v].data);

    for (ArcNode *arc = G.vertices[v].firstarc; arc != NULL; arc = arc->next) {
        int w = arc->adjvex;
        if (visited[w] == 0) {
            DFS(G, w, visited);
        }
    }
}

// 广度优先遍历
void BFS(ALGraph G, int v, int visited[]) {
    int queue[MAX_VERTEX_NUM], front = 0, rear = 0;
    printf("%c ", G.vertices[v].data);
    visited[v] = 1;
    queue[rear++] = v;

    while (front < rear) {
        int w = queue[front++];
        for (ArcNode *arc = G.vertices[w].firstarc; arc != NULL; arc = arc->next) {
            int u = arc->adjvex;
            if (visited[u] == 0) {
                printf("%c ", G.vertices[u].data);
                visited[u] = 1;
                queue[rear++] = u;
            }
        }
    }
}

int main() {
    ALGraph G;
    CreateGraph(&G);

    printf("深度优先遍历结果：");
    int visited[MAX_VERTEX_NUM] = {0};
    for (int i = 0; i < G.vexnum; i++) {
        if (visited[i] == 0) {
            DFS(G, i, visited);
        }
    }

    printf("\n广度优先遍历结果：");
    for (int i = 0; i < G.vexnum; i++) {
        visited[i] = 0;
    }
    for (int i = 0; i < G.vexnum; i++) {
        if (visited[i] == 0) {
            BFS(G, i, visited);
        }
    }

    return 0;
}

注：代码中使用了队列来实现广度优先遍历。