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

图遍历，说白了就是怎么把图里的每个节点都走一遍。我刚开始学的时候觉得这有什么难的，不就是挨个访问吗？后来在项目中处理一个百万节点的社交网络图时才发现，遍历顺序选不对，内存直接爆掉。嗯，今天咱们就把深度优先搜索（DFS）和广度优先搜索（BFS）彻底讲透。

一、图的存储结构

在讲遍历之前，得先确定图怎么存。我个人习惯用邻接表，尤其是稀疏图的时候，省内存。当然，邻接矩阵在判断两点是否相连时更快，但空间开销大。

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

// 图结构
typedef struct Graph {
    int numVertices;
    AdjNode** adjLists;
    int* visited;  // 遍历时用
} Graph;

这里visited数组很关键。我曾经在调试一个死循环时，找了半天才发现是忘记重置visited标志了。你想想看，图里如果有环，不标记已访问节点，DFS就会无限递归下去。

二、深度优先搜索（DFS）

2.1 递归实现

DFS的思路很简单：从一个节点出发，一直往深处走，走不动了就回溯。递归实现最直观，代码也最短。

void DFS_Recursive(Graph* graph, int startVertex) {
    graph->visited[startVertex] = 1;
    printf("访问节点: %d\n", startVertex);

    AdjNode* temp = graph->adjLists[startVertex];
    while (temp != NULL) {
        int adjVertex = temp->vertex;
        if (!graph->visited[adjVertex]) {
            DFS_Recursive(graph, adjVertex);
        }
        temp = temp->next;
    }
}

这里有个细节：递归深度等于图的直径。我在项目中遇到过一张深度为5000的图，递归直接栈溢出了。所以生产环境中，我建议用栈实现。

2.2 栈实现

栈实现其实就是模拟递归的过程。手动维护一个栈，把待访问节点压进去。

void DFS_Stack(Graph* graph, int startVertex) {
    int stack[1000];
    int top = -1;

    stack[++top] = startVertex;
    graph->visited[startVertex] = 1;

    while (top != -1) {
        int currentVertex = stack[top--];
        printf("访问节点: %d\n", currentVertex);

        AdjNode* temp = graph->adjLists[currentVertex];
        while (temp != NULL) {
            int adjVertex = temp->vertex;
            if (!graph->visited[adjVertex]) {
                stack[++top] = adjVertex;
                graph->visited[adjVertex] = 1;
            }
            temp = temp->next;
        }
    }
}

三、广度优先搜索（BFS）

BFS像水波一样一层层扩散。它天然适合求最短路径，因为第一次访问到目标节点时，路径一定最短。

void BFS_Queue(Graph* graph, int startVertex) {
    int queue[1000];
    int front = 0, rear = 0;

    queue[rear++] = startVertex;
    graph->visited[startVertex] = 1;

    while (front != rear) {
        int currentVertex = queue[front++];
        printf("访问节点: %d\n", currentVertex);

        AdjNode* temp = graph->adjLists[currentVertex];
        while (temp != NULL) {
            int adjVertex = temp->vertex;
            if (!graph->visited[adjVertex]) {
                queue[rear++] = adjVertex;
                graph->visited[adjVertex] = 1;
            }
            temp = temp->next;
        }
    }
}

BFS和DFS的栈实现其实很像，就是一个用栈（后进先出），一个用队列（先进先出）。你想想看，这个区别导致了完全不同的遍历顺序。

四、连通分量判定

什么叫连通分量？就是图里那些"抱团"的节点群。一个连通分量里的任意两个节点都能通过路径相连，不同分量之间则没有路径。

判定方法很简单：对每个未访问的节点执行一次DFS或BFS，每次遍历到的所有节点就是一个连通分量。

int countConnectedComponents(Graph* graph) {
    int count = 0;

    // 重置visited数组
    for (int i = 0; i < graph->numVertices; i++) {
        graph->visited[i] = 0;
    }

    for (int i = 0; i < graph->numVertices; i++) {
        if (!graph->visited[i]) {
            count++;
            printf("连通分量 %d: ", count);
            DFS_Recursive(graph, i);
            printf("\n");
        }
    }
    return count;
}

五、三种遍历策略对比

算法	数据结构	空间复杂度	时间复杂度	适用场景
DFS递归	系统栈	O(V)	O(V+E)	小图、路径搜索
DFS栈	手动栈	O(V)	O(V+E)	大图、避免栈溢出
BFS队列	队列	O(V)	O(V+E)	最短路径、层次遍历

六、知识体系总览

下面这张图把本章的核心逻辑串起来了。从图的存储出发，到两种遍历策略，再到连通分量判定，每一步都有对应的数据结构和实现方式。

好了，图遍历的核心就这些。记住：DFS适合"是否存在路径"这类问题，BFS适合"最短路径是多少"。连通分量判定则是两者的基础应用。代码写多了你会发现，这些算法本质上就是"数据结构+访问顺序"的组合游戏。