写一个图的广度和深度遍历的算法用C语言

下面是基于邻接矩阵存储的无向图的广度优先遍历和深度优先遍历算法的C语言实现：

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

#define MAX_VERTEX_NUM 100    // 最大顶点数

// 邻接矩阵存储的图
typedef struct {
    char vexs[MAX_VERTEX_NUM];    // 顶点集合
    int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];    // 邻接矩阵
    int vexnum, arcnum;    // 顶点数和边数
} Graph;

// 初始化一个无向图
void initGraph(Graph* G) {
    printf("请输入顶点数和边数：\n");
    scanf("%d%d", &G->vexnum, &G->arcnum);
    getchar();    // 消耗掉输入缓冲区中的换行符
    printf("请输入顶点集合：\n");
    for (int i = 0; i < G->vexnum; i++) {
        scanf("%c", &G->vexs[i]);
        getchar();    // 消耗掉输入缓冲区中的换行符
    }
    // 初始化邻接矩阵
    for (int i = 0; i < G->vexnum; i++) {
        for (int j = 0; j < G->vexnum; j++) {
            G->arcs[i][j] = 0;
        }
    }
    printf("请输入边的信息：\n");
    for (int k = 0; k < G->arcnum; k++) {
        char v1, v2;
        int i, j;
        printf("请输入第%d条边的两个顶点：\n", k + 1);
        scanf("%c%c", &v1, &v2);
        getchar();    // 消耗掉输入缓冲区中的换行符
        // 查找顶点在顶点集合中的下标
        for (i = 0; i < G->vexnum; i++) {
            if (G->vexs[i] == v1) {
                break;
            }
        }
        for (j = 0; j < G->vexnum; j++) {
            if (G->vexs[j] == v2) {
                break;
            }
        }
        G->arcs[i][j] = 1;    // i和j之间有一条边
        G->arcs[j][i] = 1;    // 因为是无向图，所以j和i之间也有一条边
    }
}

// 从顶点v开始深度优先遍历图
void DFS(Graph G, int v, bool visited[]) {
    visited[v] = true;
    printf("%c ", G.vexs[v]);
    for (int i = 0; i < G.vexnum; i++) {
        if (G.arcs[v][i] == 1 && !visited[i]) {
            DFS(G, i, visited);
        }
    }
}

// 深度优先遍历图
void DFSTraverse(Graph G) {
    bool visited[MAX_VERTEX_NUM];    // 标记顶点是否被访问过
    for (int i = 0; i < G.vexnum; i++) {
        visited[i] = false;
    }
    printf("深度优先遍历结果：\n");
    for (int i = 0; i < G.vexnum; i++) {
        if (!visited[i]) {
            DFS(G, i, visited);
        }
    }
    printf("\n");
}

// 从顶点v开始广度优先遍历图
void BFS(Graph G, int v, bool visited[]) {
    int queue[MAX_VERTEX_NUM];    // 定义一个队列
    int front = 0, rear = 0;    // 队头和队尾指针
    visited[v] = true;
    printf("%c ", G.vexs[v]);
    queue[rear++] = v;    // 入队
    while (front != rear) {
        int w = queue[front++];    // 出队
        for (int i = 0; i < G.vexnum; i++) {
            if (G.arcs[w][i] == 1 && !visited[i]) {
                visited[i] = true;
                printf("%c ", G.vexs[i]);
                queue[rear++] = i;    // 入队
            }
        }
    }
}

// 广度优先遍历图
void BFSTraverse(Graph G) {
    bool visited[MAX_VERTEX_NUM];    // 标记顶点是否被访问过
    for (int i = 0; i < G.vexnum; i++) {
        visited[i] = false;
    }
    printf("广度优先遍历结果：\n");
    for (int i = 0; i < G.vexnum; i++) {
        if (!visited[i]) {
            BFS(G, i, visited);
        }
    }
    printf("\n");
}

int main() {
    Graph G;
    initGraph(&G);
    DFSTraverse(G);
    BFSTraverse(G);
    return 0;
}

这段代码中，我们先定义了一个 `Graph` 结构体来表示邻接矩阵存储的图，包括顶点集合和邻接矩阵等信息。然后，我们通过 `initGraph` 函数从用户输入中构建了一个无向图。接下来，我们分别实现了深度优先遍历和广度优先遍历算法，其中 `DFS` 函数表示从顶点v开始深度优先遍历图，`BFS` 函数表示从顶点v开始广度优先遍历图。最后，在 `main` 函数中调用 `DFSTraverse` 函数和 `BFSTraverse` 函数分别输出深度优先遍历和广度优先遍历的结果。