拓扑排序首先先上网查一下定义拓扑排序Topological Sorting是针对有向无环图DAG, Directed Acyclic Graph的一种排序方式。在这种排序中图中的所有顶点被排列成一个线性序列满足若从顶点A到顶点B有一条路径则顶点A必须在序列中出现在顶点B之前。这样的序列称为满足拓扑次序的序列或简称为拓扑序列。注由于本文章作者是一个看到这种定义就头晕的人喜欢有例子讲解所以本文基于这个原因用一个排队例子展开先把定义浓缩一下把一个有向无环图DAG的所有顶点排成一个线性序列使得对于每条有向边 u → v顶点 u 都在 v 的前面例子想象你在排队打饭有个规矩如果 A 是 B 的学长那 A 必须排在 B 前面。现在给你一份名单写着谁是谁的学长。你要排出一条队伍让所有学长都在自己学弟的前面。而这个队伍的顺序就叫拓扑排序。名单和关系有 3 个人小刚、小红、小明。关系小红是小明的学长小红 → 小明小刚是小红的学长小刚 → 小红我们可以轻松得出队伍为小刚 → 小红 → 小明其中箭头方向指向谁谁就排在后面或者脑子想象一下:(饭堂打饭窗口小刚 → 小红 → 小明箭头指向方向为队伍展开方向例子有了开始对定义进行理解1.有向无环图为什么必须无环假设有环则关系变成这样小红是小明的学长小红 → 小明小明是小刚的学长小明 → 小刚小刚是小红的学长小刚 → 小红图小刚 → →小红↑ *************↓******小明看箭头就好*是我想让这个看起来好看一点如果大家觉得不好看可以自己在草稿纸上画一下这就是一个环小刚 → 小红 → 小明 → 小刚但是拓扑排序形式化定义如果有边 u → v那么 u 必须排在 v 前面。放到我们假设有环的例子里面小红既要排在小刚前面又要排在小刚后面显然一个人不能既在前面又在后面矛盾了所以我们就把有向无环图理解了优秀对于定义有了认识那做一下题目吧坏笑洛谷B3644 【模板】拓扑排序 / 家谱树题目描述有个人的家族很大辈分关系很混乱请你帮整理一下这种关系。给出每个人的后代的信息。输出一个序列使得每个人的后辈都比那个人后列出。输入格式第 1 行一个整数 N表示家族的人数。接下来 N 行第 i 行描述第 i 个人的后代编号表示 是 i 的后代。每行最后是 0 表示描述完毕。输出格式输出一个序列使得每个人的后辈都比那个人后列出。如果有多种不同的序列输出任意一种即可。样例输入504 5 1 01 05 3 03 0输出2 4 5 3 1对样例翻译一下1号没孩子2号孩子是 4号、5号、1号3号孩子是 1号4号孩子是 5号、3号5号孩子是 3号本题涉及拓扑排序的 Kahn 算法用于解决“家谱树”问题给定每个人的后代要求输出一种辈分序列使得每个人的后辈都在自己之后。看到这个不用怕我们一点点展开讲解先给出代码可AC#includebits/stdc.husingnamespacestd;intmain(){ios::sync_with_stdio(false);cin.tie(0);intn;cinn;vectorvectorintadj(n1);vectorintin_deg(n1,0);for(inti1;in;i){intv;while(cinvv!0){adj[i].push_back(v);in_deg[v];}}queueintq;for(inti1;in;i){if(in_deg[i]0){q.push(i);}}while(!q.empty()){intuq.front();q.pop();--n;if(n0){coutu ;}else{coutu\n;}for(intidx0;idxadj[u].size();idx){intvadj[u][idx];in_deg[v]in_deg[v]-1;if(in_deg[v]0){q.push(v);}}}return0;}这一段代码是输入ios::sync_with_stdio(false);cin.tie(0);intn;cinn;现在解释这个vectorvectorintadj(n1);这是 C 里一种很常见的邻接表存图方式外层 vector 的索引代表节点编号长度为 n1这样可以直接用 1 ~ n 的编号忽略第 0 个位置。内层 vector 存放该节点直接相连的邻居节点本作者依旧喜欢例子坏笑例子无向图n3有 3 个节点边是1-2, 2-3图1 —— 2 —— 3存储结果索引: 0 1 2 3adj: [ ] [2] [1,3] [2]回到题目我们写这个用来干嘛n家族人数。adj邻接表adj[i] 存储第 i 个人的所有后代编号。现在解释这个vectorintin_deg(n1,0);创建一个数组用来记录每个人的入度所以称为入度数组数组的大小是 n1并且所有元素初始值都是 0借着入度数组我们来解释一下为什么用入度不用出度入度有几个学长/学姐排在我前面有几个箭头指向我出度有几个学弟/学妹排在我后面我指向几个人箭头指向刚刚解释过在前面拓扑排序的思想是不断把“没有学长/学姐压在头上”的人叫出来排队即从前往后排的所以要一直找“前面没人了”的人而入度正好就是记录“前面还有几个人”用样例走一遍用3理解一下4和5是3的长辈所以3有2个长辈入度为2读到 2 的后代 4 → in_deg[4]4 的入度 1读到 4 的后代 5 → in_deg[5]5 的入度 1读到 2 的后代 5 → in_deg[5]5 的入度 2读到 4 的后代 3 → in_deg[3]3 的入度 1读到 5 的后代 3 → in_deg[3]3 的入度 2读到 2 的后代 1 → in_deg[1]1 的入度 1读到 3 的后代 1 → in_deg[1]1 的入度 2入度数组作用谁的入度变成 0 了让他赶紧去排队现在解释这个for(inti1;in;i){intv;while(cinvv!0){adj[i].push_back(v);in_deg[v];}}in_deg[v]先加 1再使用这个值现在解释这个queueintq;for(inti1;in;i){if(in_deg[i]0){q.push(i);}}创建队列 q存放答案如果找到有编号一开始入度为0那么就说明他前面没人先放进队列队列是先进先出现在解释这个while(!q.empty()){intu;uq.front();q.pop();--n;if(n0){coutu ;}else{coutuendl;}for(intdex0;dexadj[u].size();dex){--indeg[adj[u][dex]];if(indeg[adj[u][dex]]0){q.push(adj[u][dex]);}}}队列不为空就说明还没有处理完从队列里拿出最前面的人 u然后把他从队列里删掉这个人 u 现在可以正式输出因为他的所有长辈都已经输出完了n 原本是总人数队列少一个人就代表处理了一个人其中–n前缀自减先减 1再使用减完的值n–后缀自减先使用原来的值再减 1如果减完后 n 0说明后面还有人输出空格分隔如果减完后 n 0说明这是最后一个输出换行结束接着处理u的所有后辈adj[u] 里存的是 u 的所有后辈。这个循环意思是把 u 的每个后辈 v 拿出来处理由于 u 这个长辈已经输出了所以 v 就不用再等他。把 v 的入度还没输出的长辈数减 1如果减完后 v 的入度变成 0说明 v 所有的长辈都输出完了v 现在可以进队列等着输出了ok啊目前就写到这里吧本蒟蒻刷题去了要是刷题学会了别的知识就再完善这个笔记