企业官网建设流程全解析

拓扑排序

首先，先上网查一下定义：
拓扑排序（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 表示描述完毕。
输出格式
输出一个序列，使得每个人的后辈都比那个人后列出。如果有多种不同的序列，输出任意一种即可。

样例：
输入
5
0
4 5 1 0
1 0
5 3 0
3 0
输出
2 4 5 3 1

对样例翻译一下：
1号：没孩子
2号：孩子是 4号、5号、1号
3号：孩子是 1号
4号：孩子是 5号、3号
5号：孩子是 3号

本题涉及拓扑排序的 Kahn 算法，用于解决“家谱树”问题：给定每个人的后代，要求输出一种辈分序列，使得每个人的后辈都在自己之后。

看到这个不用怕，我们一点点展开讲解
先给出代码，可AC

#include<bits/stdc++.h>usingnamespacestd;intmain(){ios::sync_with_stdio(false);cin.tie(0);intn;cin>>n;vector<vector<int>>adj(n+1);vector<int>in_deg(n+1,0);for(inti=1;i<=n;i++){intv;while(cin>>v&&v!=0){adj[i].push_back(v);++in_deg[v];}}queue<int>q;for(inti=1;i<=n;++i){if(in_deg[i]==0){q.push(i);}}while(!q.empty()){intu=q.front();q.pop();--n;if(n>0){cout<<u<<' ';}else{cout<<u<<'\n';}for(intidx=0;idx<adj[u].size();++idx){intv=adj[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;cin>>n;

现在解释这个

vector<vector<int>>adj(n+1);

这是 C++ 里一种很常见的邻接表存图方式
外层 vector 的索引代表节点编号，长度为 n+1，这样可以直接用 1 ~ n 的编号，忽略第 0 个位置。内层 vector 存放该节点直接相连的邻居节点

本作者依旧喜欢例子（坏笑）
例子（无向图）
n=3
有 3 个节点，边是：
1-2, 2-3
图：1 —— 2 —— 3
存储结果
索引: 0 1 2 3
adj: [ ] [2] [1,3] [2]

回到题目，我们写这个用来干嘛？
n：家族人数。
adj：邻接表，adj[i] 存储第 i 个人的所有后代编号。

现在解释这个

vector<int>in_deg(n+1,0);

创建一个数组，用来记录每个人的入度，所以称为入度数组
数组的大小是 n+1，并且所有元素初始值都是 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(inti=1;i<=n;i++){intv;while(cin>>v&&v!=0){adj[i].push_back(v);++in_deg[v];}}

++in_deg[v]：先加 1，再使用这个值

现在解释这个

queue<int>q;for(inti=1;i<=n;++i){if(in_deg[i]==0){q.push(i);}}

创建队列 q，存放答案，如果找到有编号一开始入度为0，那么就说明他前面没人，先放进队列（队列是先进先出）

现在解释这个

while(!q.empty()){intu;u=q.front();q.pop();--n;if(n>0){cout<<u<<' ';}else{cout<<u<<endl;}for(intdex=0;dex<adj[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啊，目前就写到这里吧，本蒟蒻刷题去了，要是刷题学会了别的知识就再完善这个笔记