【优选算法篇】拓扑排序——逻辑先后与任务依赖的终极拆解

文章目录逻辑的枷锁在依赖网中寻找出路零、 拓扑排序打破逻辑混乱的“秩序之光”一、 课程表 I II经典拓扑排序 (Medium)1.1 题目描述1.2 算法思路依赖关系的剥离1.3 C 代码实战 (以课程表 II 为例)二、 火星词典推导未知的秩序 (Hard)2.1 题目描述2.2 深度拆解如何从对比中提取“边”2.3 C 代码实战三、 总结依赖关系的终结者逻辑的枷锁在依赖网中寻找出路零、 拓扑排序打破逻辑混乱的“秩序之光”底层逻辑什么是拓扑排序想象你在做一个大型工程有些工序必须在其他工序之后才能开始。这种“先后顺序”在图论中表现为一条有向边u → v u \to vu→v即想要完成v vv必须先搞定u uu。拓扑排序的数学定义有向无环图DAG只有不形成“死循环”的依赖关系才能排序。如果 A 依赖 BB 又依赖 A这就是逻辑死锁。入度In-degree指向该节点的边的数量。入度为 0意味着这个节点“自由”了不再被任何先置条件限制可以立即执行。Kahn 算法基于 BFS 的经典实现核心流程第一步统计入度遍历整张图计算每个节点的入度并用邻接表存储图结构。第二步寻找起点将所有初始入度为 0 的节点塞进队列。第三步剥离依赖弹出队头把它指向的所有邻居的入度减 1。这相当于“完成了当前任务解除了它对后续任务的限制”。第四步循环触发如果邻居的入度被减到了 0说明它的所有先修条件都已满足立刻入队。第五步结果判定如果处理过的节点数等于总节点数排序成功否则图中一定存在环。一、 课程表 I II经典拓扑排序 (Medium)1.1 题目描述题目链接207. 课程表 210. 课程表 II描述你总共有n门课要选。给定先修关系数组prerequisites其中[a, b]表示学a前必须先学b即b → a b \to ab→a。课程表 I只需判断是否能修完所有课。课程表 II要求返回一个可行的修课顺序。若有环则返回空数组。1.2 算法思路依赖关系的剥离这是拓扑排序最直接的建模场景。建立模型课程是节点[a, b]代表一条由b指向a的有向边b → a b \to ab→a。入度统计使用数组inDegree。若存在b - a则inDegree[a]。BFS 逻辑队列q存储当前“可以立刻修读”的课入度为 0。每修完一门课弹出q其后续课程的负担就减轻了邻居入度 -1。只要邻居的入度清零它就变成了“可以修读”的状态进入队列。1.3 C 代码实战 (以课程表 II 为例)classSolution{public:vectorintfindOrder(intn,vectorvectorintprerequisites){// 1. 准备邻接表和入度统计数组vectorvectorintedges(n);vectorintinDegree(n,0);// 2. 建图prerequisites[i] [a, b] 表示 b 必须在 a 之前// 所以建立一条有向边b - afor(autop:prerequisites){intap[0],bp[1];edges[b].push_back(a);inDegree[a];}// 3. 将所有入度为 0 的节点没有任何前置要求的课入队queueintq;for(inti0;in;i){if(inDegree[i]0)q.push(i);}// 4. BFS 拓扑排序不断解除依赖vectorintresult;while(!q.empty()){inttq.front();q.pop();result.push_back(t);// 记录下这门课// 遍历这门课的所有后续课程解除它们的依赖for(intneighbor:edges[t]){inDegree[neighbor]--;if(inDegree[neighbor]0){q.push(neighbor);// 依赖全部清除可以学了}}}// 5. 最终判定若处理过的课程数等于 n说明无环if(result.size()n)returnresult;return{};// 有环无法修完}};二、 火星词典推导未知的秩序 (Hard)2.1 题目描述题目链接LCR 114. 火星词典描述给定一个按火星语字典序排好序的单词列表words。请你根据这些单词的相对顺序推导出火星字母的先后顺序。若不存在合法顺序如存在环返回空字符串。2.2 深度拆解如何从对比中提取“边”这道题是拓扑排序的高阶应用重点在于如何自己发现依赖关系。字符集识别先统计出所有出现过的字符每个字符都是图中的一个节点。比较相邻单词依赖关系隐藏在相邻单词的第一处不同。例如words[i] wrtwords[i1] wrf。逐位对比第 1 位 ‘w’ 相同第 2 位 ‘r’ 相同第 3 位出现不同‘t’ vs ‘f’。关键结论在火星语中‘t’ 排在 ‘f’ 前。建立有向边t - f并增加 ‘f’ 的入度。注意一旦找到第一对不同的字符该单词对的对比立即结束后面的位没有参考价值。前缀异常处理如果words[i1]是words[i]的前缀如apple在app前面这在任何字典序里都是非法的直接判死刑返回。运行拓扑剩下的就是标准的 BFS 逻辑。2.3 C 代码实战classSolution{unordered_mapchar,vectorchargraph;// 邻接表unordered_mapchar,intinDegree;// 统计每个字母的入度boolisInvalidfalse;// 标记非法前缀情况public:stringalienOrder(vectorstringwords){// 1. 初始化只为出现过的字符建立入度记录for(conststringword:words){for(charch:word)inDegree[ch]0;}// 2. 遍历单词对对比建图intnwords.size();for(inti0;in-1;i){buildEdges(words[i],words[i1]);if(isInvalid)return;}// 3. 准备队列入度为 0 的火星字母queuecharq;for(autoentry:inDegree){if(entry.second0)q.push(entry.first);}// 4. 标准拓扑排序逻辑string res;while(!q.empty()){charcurrq.front();q.pop();rescurr;for(charneighbor:graph[curr]){inDegree[neighbor]--;if(inDegree[neighbor]0){q.push(neighbor);}}}// 5. 判环结果字符串长度应等于不同字母的总数returnres.size()inDegree.size()?res:;}private:voidbuildEdges(conststrings1,conststrings2){intlenmin(s1.size(),s2.size());intj0;for(;jlen;j){if(s1[j]!s2[j]){// 发现第一对不同字母建立 s1[j] - s2[j] 的关系charfroms1[j],tos2[j];// 检查是否已经是重复边避免干扰入度统计boolexistfalse;for(charc:graph[from])if(cto)existtrue;if(!exist){graph[from].push_back(to);inDegree[to];}break;// 找到第一对不同就必须停下}}// 特殊边界如果 s2 是 s1 的前缀如 abc, ab非法if(js2.size()s1.size()s2.size())isInvalidtrue;}};三、 总结依赖关系的终结者复盘总结拓扑排序不仅是一个算法更是一种处理“先后限制”的工业级方案。核心在于入度入度反映了任务的受限程度。建图是门艺术有时候边是题目给的课程表有时候边需要你通过对比逻辑自己去挖掘火星词典。判环是杀手锏只要处理完的节点数对不上总数逻辑中必定存在互相等待的死结。