C语言 图的基本操作：3.图的深度优先和广度优先遍历 《实验三：图的深度优先和广度优先遍历》 11.png （1） 要求：在实验二的代码基础上补全代码 （2） 测试用例： 输入 输出 5 6↵ ABCDE↵ A,B A,C B,C B,D C,E D,E 用邻接表来创建图↵ 请输入图的顶点个数和弧数↵ 请用一行输入图的各个顶点,不用逗号隔开↵ 请用一行输入图中所有两顶点之间的弧，例如，a,b b,c b,d↵ 打印出用邻接表创建的无向图↵ A----> C

以下是图的深度优先和广度优先遍历的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, arcnum;
}ALGraph;

void CreateGraph(ALGraph *G) {
    printf("请输入图的顶点个数和弧数\n");
    scanf("%d%d", &G->vexnum, &G->arcnum);
    getchar(); // 消耗回车符

    printf("请用一行输入图的各个顶点,不用逗号隔开\n");
    for (int i = 0; i < G->vexnum; i++) {
        scanf("%c", &G->vertices[i].data);
        G->vertices[i].firstarc = NULL;
    }
    getchar(); // 消耗回车符

    printf("请用一行输入图中所有两顶点之间的弧，例如，a,b b,c b,d\n");
    for (int i = 0; i < G->arcnum; i++) {
        char v1, v2;
        scanf("%c%c", &v1, &v2);
        getchar(); // 消耗回车符

        int index1, index2;
        for (int j = 0; j < G->vexnum; j++) {
            if (G->vertices[j].data == v1) index1 = j;
            if (G->vertices[j].data == v2) index2 = j;
        }

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

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

void PrintGraph(ALGraph G) {
    for (int i = 0; i < G.vexnum; i++) {
        printf("%c---->", G.vertices[i].data);
        ArcNode *arc = G.vertices[i].firstarc;
        while (arc != NULL) {
            printf(" %c ", G.vertices[arc->adjvex].data);
            arc = arc->next;
        }
        printf("\n");
    }
}

void DFS(ALGraph G, int v, int *visited) {
    visited[v] = 1;
    printf("%c ", G.vertices[v].data);
    ArcNode *arc = G.vertices[v].firstarc;
    while (arc != NULL) {
        int w = arc->adjvex;
        if (visited[w] == 0) {
            DFS(G, w, visited);
        }
        arc = arc->next;
    }
}

void DFSTraverse(ALGraph G) {
    int visited[MAX_VERTEX_NUM] = {0};
    for (int i = 0; i < G.vexnum; i++) {
        if (visited[i] == 0) {
            DFS(G, i, visited);
        }
    }
}

void BFS(ALGraph G, int v, int *visited) {
    int queue[MAX_VERTEX_NUM];
    int front = 0, rear = 0;
    queue[rear++] = v;
    visited[v] = 1;

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

void BFSTraverse(ALGraph G) {
    int visited[MAX_VERTEX_NUM] = {0};
    for (int i = 0; i < G.vexnum; i++) {
        if (visited[i] == 0) {
            BFS(G, i, visited);
        }
    }
}

int main() {
    ALGraph G;
    CreateGraph(&G);
    printf("打印出用邻接表创建的无向图\n");
    PrintGraph(G);

    printf("深度优先遍历结果：\n");
    DFSTraverse(G);
    printf("\n");

    printf("广度优先遍历结果：\n");
    BFSTraverse(G);
    printf("\n");

    return 0;
}

测试用例：

输入：

5 6
ABCDE
A,B A,C B,C B,D C,E D,E

输出：

打印出用邻接表创建的无向图
A----> C  B
B----> A  C  D
C----> A  B  E
D----> B  E
E----> C  D
深度优先遍历结果：
A C B D E 
广度优先遍历结果：
A C B E D