本文共 2187 字，大约阅读时间需要 7 分钟。

深度优先遍历（DFS）和广度优先遍历（BFS）是图遍历算法中的两种重要方法。这些算法在程序设计中常用于查找图中的路径、连通区域或识别图的各种属性。以下是关于这两种算法的详细说明。

深度优先遍历（DFS）

DFS是一种以栈数据结构为基础的遍历算法。与BFS（队列）不同，DFS会尽可能深入递归遍历每一个可达的节点。其核心思想是：进入节点后，尽可能深入访问该节点的子节点，而不是访问顺序上的下一个节点。

代码示例解析

void DFS(ALGraph *G, int v) {    ArcNode *p;    int w;    visited[v] = 1;    printf("%d ", v);    p = G->adjlist[v].firstarc;    while (p != NULL) {        w = p->adjvex;        if (visited[w] == 0)            DFS(G, w);        p = p->nextarc;    }}

测试图示

测试使用的图结构如下：

1 <-> 2 <-> 3|      |      |8 <-> 4 <-> 5|      |6 <-> 7

优势：

• DFS能够在图中找到哈密尔顿路径或环。
• 适合处理树和� Trails结构。
• 适用于需要预先知道深度信息的场景。

广度优先遍历（BFS）

BFS是一种以队列数据结构为基础的遍历算法。其核心思想是：从起点出发，一层一层地访问邻接节点，确保每一层的节点都被访问过后才访问下一层。这与 DFS 的区别在于，BFS更注重访问节点的层数。

代码示例解析

void BFS(ALGraph *G, int v) {    ArcNode *p;    int w, i;    etext int queue[MAXV], front = 0, rear = 0;    int visited[MAXV];        for (i = 0; i < G->n; i++) {        visited[i] = 0;    }        printf("%2d", v);    visited[v] = 1;    rear = (rear + 1) % MAXV;    queue[rear] = v;        while (front != rear) {        front = (front + 1) % MAXV;        w = queue[front];        p = G->adjlist[w].firstarc;                while (p != NULL) {            if (visited[p->adjvex] == 0) {                printf("%2d", p->adjvex);                visited[p->adjvex] = 1;                rear = (rear + 1) % MAXV;                queue[rear] = p->adjvex;            }            p = p->nextarc;        }    }    printf("\n");}

测试图示

与DFS相同，测试图结构如下：

1 <-> 2 <-> 3|      |      |8 <-> 4 <-> 5|      |6 <-> 7

优势：

• BFS能够找到图的最短路径。
• 适合处理网格或层级结构的图。
• 适用于需要访问顺序不影响结果的场景，比如任务调度。

总结

两种遍历算法各有优势：

• DFS：适合预先知道深度信息的场景，能够找到哈密尔顿路径。
• BFS：擅长找到最短路径，适合网格和层级结构。

通过合理选择算法，可以更好地解决实际问题。