图的深度优先遍历与广度优先遍历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 *first;
} VNode, AdjList[MAX_VERTEX_NUM];

typedef struct {
    AdjList vertices;
    int vexnum, arcnum;
} ALGraph;

int visited[MAX_VERTEX_NUM];

void CreateGraph(ALGraph *G) {
    printf("请输入顶点数和边数：");
    scanf("%d%d", &G->vexnum, &G->arcnum);
    getchar();
    printf("请输入各个顶点的信息：\n");
    for (int i = 0; i < G->vexnum; i++) {
        printf("第%d个顶点：", i + 1);
        scanf("%c", &G->vertices[i].data);
        G->vertices[i].first = NULL;
        getchar();
    }
    printf("请输入各个边的信息：\n");
    for (int k = 0; k < G->arcnum; k++) {
        char v1, v2;
        int i, j;
        printf("第%d条边：", k + 1);
        scanf("%c%c", &v1, &v2);
        getchar();
        for (i = 0; i < G->vexnum; i++) {
            if (G->vertices[i].data == v1) {
                break;
            }
        }
        for (j = 0; j < G->vexnum; j++) {
            if (G->vertices[j].data == v2) {
                break;
            }
        }
        ArcNode *p = (ArcNode *)malloc(sizeof(ArcNode));
        p->adjvex = j;
        p->next = G->vertices[i].first;
        G->vertices[i].first = p;
        p = (ArcNode *)malloc(sizeof(ArcNode));
        p->adjvex = i;
        p->next = G->vertices[j].first;
        G->vertices[j].first = p;
    }
}

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

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

int main() {
    ALGraph G;
    CreateGraph(&G);
    printf("深度优先遍历结果为：");
    DFSTraverse(G);
    printf("\n");
    return 0;
}

广度优先遍历：

#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 *first;
} VNode, AdjList[MAX_VERTEX_NUM];

typedef struct {
    AdjList vertices;
    int vexnum, arcnum;
} ALGraph;

int visited[MAX_VERTEX_NUM];

void CreateGraph(ALGraph *G) {
    printf("请输入顶点数和边数：");
    scanf("%d%d", &G->vexnum, &G->arcnum);
    getchar();
    printf("请输入各个顶点的信息：\n");
    for (int i = 0; i < G->vexnum; i++) {
        printf("第%d个顶点：", i + 1);
        scanf("%c", &G->vertices[i].data);
        G->vertices[i].first = NULL;
        getchar();
    }
    printf("请输入各个边的信息：\n");
    for (int k = 0; k < G->arcnum; k++) {
        char v1, v2;
        int i, j;
        printf("第%d条边：", k + 1);
        scanf("%c%c", &v1, &v2);
        getchar();
        for (i = 0; i < G->vexnum; i++) {
            if (G->vertices[i].data == v1) {
                break;
            }
        }
        for (j = 0; j < G->vexnum; j++) {
            if (G->vertices[j].data == v2) {
                break;
            }
        }
        ArcNode *p = (ArcNode *)malloc(sizeof(ArcNode));
        p->adjvex = j;
        p->next = G->vertices[i].first;
        G->vertices[i].first = p;
        p = (ArcNode *)malloc(sizeof(ArcNode));
        p->adjvex = i;
        p->next = G->vertices[j].first;
        G->vertices[j].first = p;
    }
}

void BFS(ALGraph G, int v) {
    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++];
        ArcNode *p = G.vertices[w].first;
        while (p) {
            if (!visited[p->adjvex]) {
                printf("%c ", G.vertices[p->adjvex].data);
                visited[p->adjvex] = 1;
                queue[rear++] = p->adjvex;
            }
            p = p->next;
        }
    }
}

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

int main() {
    ALGraph G;
    CreateGraph(&G);
    printf("广度优先遍历结果为：");
    BFSTraverse(G);
    printf("\n");
    return 0;
}