04-图——从BFS、DFS到拓扑排序

老程序员回炉补基础（四）：图——从 BFS、DFS 到拓扑排序

图是数据结构中最复杂的一种，也是最贴近现实世界的。社交网络、地图导航、任务调度、网络拓扑……图无处不在。我用邻接表实现了一个通用的图结构，并实现了广度优先搜索、深度优先搜索和拓扑排序。

图的数据结构设计

我选择了邻接表来表示图，即每个顶点维护一个链表，存储与之相连的边。

顶点（Vertex）

publicclassVertex<T>{privateintcode;// 顶点编号privateTdata;// 顶点数据privateEdgenext;// 指向与该顶点相连的第一条边}

边（Edge）

publicclassEdge{privateintcode;// 指向的顶点编号privateintweigth;// 权重privateEdgenext;// 指向下一条边（链表）}

图（Graph）

publicclassGraph<T>{privateVertex<T>[]vertexs;// 顶点集合privateintvisitor[];// 访问标志}

构建测试图

// 5个顶点：v0, v1, v2, v3, v4// 边：// v0 → v1(w=10), v0 → v2(w=1), v0 → v4(w=6)// v1 → v3, v1 → v4(w=7)// v2 → v3// v4 → v2(w=8), v4 → v3(w=4)

对应的有向图：

v0 ──10──→ v1 │ │ \ 1 6 7 \ │ / │ \ ↓↙ ↓ ↓ v2 ──→ v4 ──4─→v3 8↗

一、广度优先搜索（BFS）

学习时间：2023年10月17日

publicvoidBSF(inti)throwsException{mQueue<Integer>q=newmQueue<Integer>();q.inQueue(newqNode<Integer>(i));while(q.getCurrSize()>0){intcode=q.outQueue().getData();Vertex<T>v=vertexs[code];if(visitor[code]==0){System.out.println(v.getData());visitor[code]=1;}Edgee=v.getNext();while(e!=null){intvi=e.getCode();q.inQueue(newqNode<Integer>(vi));e=e.getNext();}}}

我的理解

BFS 就像水波纹一样，从起点一层一层向外扩展。用队列实现：

1. 起点入队
2. 出队一个顶点，访问它，把它所有未访问的邻居入队
3. 重复直到队列为空

执行过程（从 v0 开始）：

1. 入队 v0 2. 出队 v0，打印 v0，入队 v1, v2, v4 3. 出队 v1，打印 v1，入队 v3, v4 4. 出队 v2，打印 v2，入队 v3 5. 出队 v4，打印 v4，入队 v2, v3 6. v3 已在队列中但未访问，出队 v3，打印 v3 ...

注意：我在代码中把 BFS 写成了BSF，DFS 写成了DSF——字母顺序写反了。这是凭记忆手写时的典型错误，也侧面说明这些代码是原创的。

二、深度优先搜索（DFS）

publicvoidDSF(inti){Vertex<T>v=vertexs[i];if(visitor[i]==0){System.out.println(v.getData());visitor[i]=1;}Edgee=v.getNext();if(e!=null){if(visitor[e.getCode()]==0){DSF(e.getCode());}while(e.getNext()!=null){e=e.getNext();if(visitor[e.getCode()]==0){DSF(e.getCode());}}}}

我的理解

DFS 就像走迷宫——沿着一条路一直走到底，走不通了就回退到上一个岔路口，换一条路继续走。用递归（或栈）实现：

1. 访问当前顶点
2. 遍历它的所有邻居，对未访问的邻居递归执行 DFS

BFS vs DFS 对比：

三、拓扑排序（Topological Sort）

学习时间：2023年10月17日

publicvoidTopo()throwsException{// 1. 计算所有顶点的入度intver[]=newint[vertexs.length];for(inti=0;i<ver.length;i++){ver[i]=0;}for(inti=0;i<vertexs.length;i++){Edgee=vertexs[i].getNext();while(e!=null){ver[e.getCode()]++;e=e.getNext();}}// O(V*E)// 2. 入度为 0 的顶点入队mQueue<Integer>q=newmQueue<Integer>();for(inti=0;i<ver.length;i++){if(ver[i]==0){q.inQueue(newqNode<Integer>(i));}}// 3. 不断出队，减少邻居的入度，入度为 0 的再入队while(q.getCurrSize()>0){intv=q.outQueue().getData();Edgee=vertexs[v].getNext();System.out.println(vertexs[v].getData());while(e!=null){ver[e.getCode()]--;if(ver[e.getCode()]==0){q.inQueue(newqNode<Integer>(e.getCode()));}e=e.getNext();}}}

我的理解

拓扑排序解决的是"有先后依赖关系的任务，应该按什么顺序执行"的问题。比如：

• 课程 A 是课程 B 的先修课，必须先学 A
• Maven 的模块依赖，必须先编译被依赖的模块
• Dockerfile 的构建步骤有先后顺序

算法用Kahn算法（入度法）：

1. 计算每个顶点的入度（有多少条边指向它）
2. 入度为 0 的顶点没有前置依赖，可以先处理，入队
3. 处理一个顶点后，把它指向的邻居的入度减 1
4. 如果某个邻居的入度变为 0，说明它的前置依赖都处理完了，入队
5. 重复直到所有顶点都处理完

如果最后有顶点没被处理，说明图中有环（循环依赖），拓扑排序无法完成。

架构师视角

拓扑排序在工程中无处不在：

• Maven/Gradle的依赖解析
• CI/CD Pipeline的任务编排
• 微服务的启动顺序（服务 A 依赖服务 B，必须先启动 B）
• 数据库的表结构迁移（外键约束导致有先后顺序）

理解了拓扑排序，你才能真正理解为什么循环依赖是架构设计中的大忌。

四、未完成的 Prim 最小生成树

publicintPrim(inti){intvers[]=newint[vertexs.length];return0;}

这是我学习过程中的一个"遗憾"。Prim算法的最小生成树我只写了签名和初始化，没有完成实现。这说明当时学到这个地方时，可能因为工作或者其他原因中断了。

不过这种"未完成"也真实地反映了自学的状态——不可能每个知识点都一次吃透，重要的是保持学习的节奏，以后再回来补上。

图的算法总结

下一篇预告：《老程序员回炉补基础（五）：经典算法——背包、LCS、N皇后、汉诺塔》