用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;

// 初始化邻接表
void InitGraph(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 i = 0; i < G->arcnum; i++) {
        int v1, v2;
        printf("第%d条边：", i + 1);
        scanf("%d %d", &v1, &v2);
        getchar(); // 吸收输入缓冲区中的换行符

        ArcNode *p1 = (ArcNode *)malloc(sizeof(ArcNode)); // 生成一个新的边结点
        p1->adjvex = v2 - 1;
        p1->next = G->vertices[v1 - 1].first; // 插入到v1的边表头部
        G->vertices[v1 - 1].first = p1;

        ArcNode *p2 = (ArcNode *)malloc(sizeof(ArcNode)); // 生成一个新的边结点
        p2->adjvex = v1 - 1;
        p2->next = G->vertices[v2 - 1].first; // 插入到v2的边表头部
        G->vertices[v2 - 1].first = p2;
    }
}

// 用队列实现广度遍历
void BFS(ALGraph *G, int v, int visited[]) {
    int queue[MAX_VERTEX_NUM], front = -1, rear = -1;
    visited[v] = 1;
    printf("%c ", G->vertices[v].data);
    queue[++rear] = v;
    while (front < rear) {
        int w = queue[++front];
        for (ArcNode *p = G->vertices[w].first; p; p = p->next) {
            int adjvex = p->adjvex;
            if (!visited[adjvex]) {
                visited[adjvex] = 1;
                printf("%c ", G->vertices[adjvex].data);
                queue[++rear] = adjvex;
            }
        }
    }
}

// 广度遍历
void BFSTraverse(ALGraph *G) {
    int visited[MAX_VERTEX_NUM] = {0}; // 初始化标记数组
    printf("广度遍历结果：");
    for (int i = 0; i < G->vexnum; i++) {
        if (!visited[i]) {
            BFS(G, i, visited);
        }
    }
    printf("\n");
}

int visited[MAX_VERTEX_NUM] = {0}; // 初始化标记数组

// 用递归实现深度遍历
void DFS(ALGraph *G, int v) {
    visited[v] = 1;
    printf("%c ", G->vertices[v].data);
    for (ArcNode *p = G->vertices[v].first; p; p = p->next) {
        int adjvex = p->adjvex;
        if (!visited[adjvex]) {
            DFS(G, adjvex);
        }
    }
}

// 深度遍历
void DFSTraverse(ALGraph *G) {
    printf("深度遍历结果：");
    for (int i = 0; i < G->vexnum; i++) {
        if (!visited[i]) {
            DFS(G, i);
        }
    }
    printf("\n");
}

// 主函数
int main() {
    ALGraph G;
    InitGraph(&G);
    BFSTraverse(&G);
    DFSTraverse(&G);
    return 0;
}

深度遍历和广度遍历的思路都比较简单，就是遍历每个顶点，然后依次访问与之相邻的顶点。不同的是，广度遍历使用队列，深度遍历使用递归。