图的广度遍历和深度遍历

图的遍历是指访问图中每个节点且仅访问一次的过程。其中，广度优先遍历（BFS）和深度优先遍历（DFS）是两种常见的图遍历算法。

广度优先遍历，即按照“广度”的方式去遍历，从起点开始，首先访问其所有的相邻节点，然后依次访问这些相邻节点的相邻节点，直到遍历完所有可达节点。使用队列作为辅助结构，每次访问一个节点时将其所有未被访问过的相邻节点放入队列中，直到队列为空为止。

深度优先遍历，则是按照“深度”的方式去遍历，从起点开始，依次访问它的第一个未被访问过的相邻节点，然后继续递归访问该节点的第一个未被访问过的相邻节点，直到所有可达节点都被访问过。使用栈作为辅助结构，每次访问一个节点时将其所有未被访问过的相邻节点放入栈中，直到栈为空为止。

相关问题

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

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

无向图的深度遍历和广度遍历

无向图的深度遍历（Depth-first search, DFS）和广度遍历（Breadth-first search, BFS）是两种常用的图遍历算法。

深度遍历：

深度遍历是以某一个顶点为起点，沿着一条路径遍历到不能再继续下去时返回上一个顶点，继续遍历下一个路径，直到遍历完整个图的过程。具体实现可以使用递归或者栈来实现。

伪代码如下：

DFS(vertex v):
visited[v] = true
for each neighbor w of v:
if visited[w] == false:
DFS(w)

广度遍历：

广度遍历是从起点开始，逐层遍历下去，每层都遍历完之后再进入下一层，直到遍历完整个图的过程。具体实现可以使用队列来实现。

伪代码如下：

BFS(vertex v):
visited[v] = true
enqueue(v)
while queue is not empty:
vertex u = dequeue()
for each neighbor w of u:
if visited[w] == false:
visited[w] = true
enqueue(w)

在实际应用中，深度遍历和广度遍历都有各自的优缺点。深度遍历可以更快地到达目标节点，但是可能会陷入死循环。广度遍历则可以找到最短路径，但是需要更多的内存空间。根据实际的需求来选择合适的算法。