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

老程序员回炉补基础四图——从 BFS、DFS 到拓扑排序图是数据结构中最复杂的一种也是最贴近现实世界的。社交网络、地图导航、任务调度、网络拓扑……图无处不在。我用邻接表实现了一个通用的图结构并实现了广度优先搜索、深度优先搜索和拓扑排序。图的数据结构设计我选择了邻接表来表示图即每个顶点维护一个链表存储与之相连的边。顶点VertexpublicclassVertexT{privateintcode;// 顶点编号privateTdata;// 顶点数据privateEdgenext;// 指向与该顶点相连的第一条边}边EdgepublicclassEdge{privateintcode;// 指向的顶点编号privateintweigth;// 权重privateEdgenext;// 指向下一条边链表}图GraphpublicclassGraphT{privateVertexT[]vertexs;// 顶点集合privateintvisitor[];// 访问标志}构建测试图// 5个顶点v0, v1, v2, v3, v4// 边// v0 → v1(w10), v0 → v2(w1), v0 → v4(w6)// v1 → v3, v1 → v4(w7)// v2 → v3// v4 → v2(w8), v4 → v3(w4)对应的有向图v0 ──10──→ v1 │ │ \ 1 6 7 \ │ / │ \ ↓↙ ↓ ↓ v2 ──→ v4 ──4─→v3 8↗一、广度优先搜索BFS学习时间2023年10月17日publicvoidBSF(inti)throwsException{mQueueIntegerqnewmQueueInteger();q.inQueue(newqNodeInteger(i));while(q.getCurrSize()0){intcodeq.outQueue().getData();VertexTvvertexs[code];if(visitor[code]0){System.out.println(v.getData());visitor[code]1;}Edgeev.getNext();while(e!null){intvie.getCode();q.inQueue(newqNodeInteger(vi));ee.getNext();}}}我的理解BFS 就像水波纹一样从起点一层一层向外扩展。用队列实现起点入队出队一个顶点访问它把它所有未访问的邻居入队重复直到队列为空执行过程从 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 写成了BSFDFS 写成了DSF——字母顺序写反了。这是凭记忆手写时的典型错误也侧面说明这些代码是原创的。二、深度优先搜索DFSpublicvoidDSF(inti){VertexTvvertexs[i];if(visitor[i]0){System.out.println(v.getData());visitor[i]1;}Edgeev.getNext();if(e!null){if(visitor[e.getCode()]0){DSF(e.getCode());}while(e.getNext()!null){ee.getNext();if(visitor[e.getCode()]0){DSF(e.getCode());}}}}我的理解DFS 就像走迷宫——沿着一条路一直走到底走不通了就回退到上一个岔路口换一条路继续走。用递归或栈实现访问当前顶点遍历它的所有邻居对未访问的邻居递归执行 DFSBFS vs DFS 对比BFSDFS数据结构队列栈或递归遍历策略逐层扩展一条路走到底空间复杂度O(V)O(V)应用最短路径无权图连通性检测、拓扑排序三、拓扑排序Topological Sort学习时间2023年10月17日publicvoidTopo()throwsException{// 1. 计算所有顶点的入度intver[]newint[vertexs.length];for(inti0;iver.length;i){ver[i]0;}for(inti0;ivertexs.length;i){Edgeevertexs[i].getNext();while(e!null){ver[e.getCode()];ee.getNext();}}// O(V*E)// 2. 入度为 0 的顶点入队mQueueIntegerqnewmQueueInteger();for(inti0;iver.length;i){if(ver[i]0){q.inQueue(newqNodeInteger(i));}}// 3. 不断出队减少邻居的入度入度为 0 的再入队while(q.getCurrSize()0){intvq.outQueue().getData();Edgeevertexs[v].getNext();System.out.println(vertexs[v].getData());while(e!null){ver[e.getCode()]--;if(ver[e.getCode()]0){q.inQueue(newqNodeInteger(e.getCode()));}ee.getNext();}}}我的理解拓扑排序解决的是有先后依赖关系的任务应该按什么顺序执行的问题。比如课程 A 是课程 B 的先修课必须先学 AMaven 的模块依赖必须先编译被依赖的模块Dockerfile 的构建步骤有先后顺序算法用Kahn算法入度法计算每个顶点的入度有多少条边指向它入度为 0 的顶点没有前置依赖可以先处理入队处理一个顶点后把它指向的邻居的入度减 1如果某个邻居的入度变为 0说明它的前置依赖都处理完了入队重复直到所有顶点都处理完如果最后有顶点没被处理说明图中有环循环依赖拓扑排序无法完成。架构师视角拓扑排序在工程中无处不在Maven/Gradle的依赖解析CI/CD Pipeline的任务编排微服务的启动顺序服务 A 依赖服务 B必须先启动 B数据库的表结构迁移外键约束导致有先后顺序理解了拓扑排序你才能真正理解为什么循环依赖是架构设计中的大忌。四、未完成的 Prim 最小生成树publicintPrim(inti){intvers[]newint[vertexs.length];return0;}这是我学习过程中的一个遗憾。Prim算法的最小生成树我只写了签名和初始化没有完成实现。这说明当时学到这个地方时可能因为工作或者其他原因中断了。不过这种未完成也真实地反映了自学的状态——不可能每个知识点都一次吃透重要的是保持学习的节奏以后再回来补上。图的算法总结算法用途数据结构时间复杂度BFS层序遍历、最短路径无权队列O(VE)DFS深度遍历、连通性检测栈/递归O(VE)拓扑排序任务排序、依赖解析队列 入度数组O(VE)Prim最小生成树优先队列O(E log V)下一篇预告《老程序员回炉补基础五经典算法——背包、LCS、N皇后、汉诺塔》