图的遍历：深度优先搜索与广度优先搜索

图遍历，说白了就是怎么把图里的所有节点都走一遍。这问题听起来简单，但实际写代码时坑不少。我最早接触这概念是在做嵌入式网络拓扑分析时，一个路由节点没遍历到，整个路径计算就全错了。

两种最经典的遍历方式：DFS（深度优先搜索）和BFS（广度优先搜索）。一个用栈，一个用队列。咱们今天就把它们彻底讲透。

深度优先搜索（DFS）—— 栈实现

DFS的思路很直接：一条路走到黑，走不通了再回头。你想想看，就像在迷宫里，你一直往深处走，直到撞墙了才退回来找另一条路。

我个人习惯用栈来实现DFS。为什么？因为栈的"后进先出"特性正好匹配"先往深处走"的需求。

DFS的代码实现

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

#define MAX_NODES 100

// 邻接表节点
typedef struct Node {
    int vertex;
    struct Node* next;
} Node;

// 图结构
typedef struct Graph {
    int numVertices;
    Node** adjLists;
    int* visited;
} Graph;

// 栈结构
typedef struct Stack {
    int items[MAX_NODES];
    int top;
} Stack;

void push(Stack* s, int value) {
    if (s->top == MAX_NODES - 1) return;
    s->items[++(s->top)] = value;
}

int pop(Stack* s) {
    if (s->top == -1) return -1;
    return s->items[(s->top)--];
}

int isEmpty(Stack* s) {
    return s->top == -1;
}

// DFS核心函数
void DFS(Graph* graph, int startVertex) {
    Stack* stack = (Stack*)malloc(sizeof(Stack));
    stack->top = -1;
    
    // 标记起点已访问并入栈
    graph->visited[startVertex] = 1;
    push(stack, startVertex);
    
    while (!isEmpty(stack)) {
        int currentVertex = pop(stack);
        printf("访问节点: %d\n", currentVertex);
        
        // 遍历当前节点的所有邻居
        Node* temp = graph->adjLists[currentVertex];
        while (temp) {
            int adjVertex = temp->vertex;
            if (!graph->visited[adjVertex]) {
                graph->visited[adjVertex] = 1;
                push(stack, adjVertex);
            }
            temp = temp->next;
        }
    }
    free(stack);
}

广度优先搜索（BFS）—— 队列实现

BFS和DFS正好相反。它是一层一层往外扩，就像往水里扔石头，波纹一圈圈扩散。

队列的"先进先出"特性完美匹配BFS的需求。你先访问的节点，它的邻居也要先被访问。

BFS的代码实现

// 队列结构
typedef struct Queue {
    int items[MAX_NODES];
    int front;
    int rear;
} Queue;

void enqueue(Queue* q, int value) {
    if (q->rear == MAX_NODES - 1) return;
    q->items[++(q->rear)] = value;
}

int dequeue(Queue* q) {
    if (q->front > q->rear) return -1;
    return q->items[(q->front)++];
}

int isQueueEmpty(Queue* q) {
    return q->front > q->rear;
}

// BFS核心函数
void BFS(Graph* graph, int startVertex) {
    Queue* queue = (Queue*)malloc(sizeof(Queue));
    queue->front = 0;
    queue->rear = -1;
    
    graph->visited[startVertex] = 1;
    enqueue(queue, startVertex);
    
    while (!isQueueEmpty(queue)) {
        int currentVertex = dequeue(queue);
        printf("访问节点: %d\n", currentVertex);
        
        Node* temp = graph->adjLists[currentVertex];
        while (temp) {
            int adjVertex = temp->vertex;
            if (!graph->visited[adjVertex]) {
                graph->visited[adjVertex] = 1;
                enqueue(queue, adjVertex);
            }
            temp = temp->next;
        }
    }
    free(queue);
}

DFS vs BFS：怎么选？

特性	DFS（栈）	BFS（队列）
数据结构	栈（后进先出）	队列（先进先出）
遍历顺序	深度优先，一条路走到底	广度优先，一层层扩散
空间复杂度	O(h)，h为树深度	O(w)，w为最大宽度
适用场景	路径搜索、拓扑排序	最短路径、层级遍历
是否保证最短路径	否	是（无权图）

知识体系总览

下面这张图把DFS和BFS的核心逻辑、数据结构、应用场景串起来了。建议你多看几遍，理解它们之间的区别和联系。

实际项目中的选择

我在做嵌入式网络协议栈时，经常需要遍历拓扑图。如果是要找两个节点之间是否存在路径，我一般用DFS，因为它实现简单、栈空间可控。但如果要算最短路径（比如路由跳数最少），那就必须上BFS。

还有一个细节：嵌入式环境内存有限。DFS的栈深度取决于图的最长路径，而BFS的队列大小取决于图的最大宽度。你得根据实际图结构来选。比如树形结构，DFS更省内存；如果是扁平结构（很多节点直接相连），BFS反而更省。

---

公众号:蓝海资料掘金营，微信deep3321