拓扑排序——讲解
拓扑排序：
对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边(u,v)∈E(G)，则u在线性序列中出现在v之前。
通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。
偏序/全序关系：
偏序和全序实际上是离散数学中的概念。
这里不打算说太多形式化的定义，形式化的定义教科书上或者网页就说的很详细。 还是以上面选课的例子来描述这两个概念。假设我们在学习完了算法这门课后，可以选修机器学习或者计算机图形学。
这个或者表示，学习机器学习和计算机图形学这两门课之间没有特定的先后顺序。
因此，在我们所有可以选择的课程中，任意两门课程之间的关系要么是确定的(即拥有先后关系)，要么是不确定的(即没有先后关系)，绝对不存在互相矛盾的关系(即环路)。
以上就是偏序的意义，抽象而言，有向图中两个顶点之间不存在环路，至于连通与否，是无所谓的。所以，有向无环图必然是满足偏序关系的。 理解了偏序的概念，那么全序就好办了。所谓全序，就是在偏序的基础之上，有向无环图中的任意一对顶点还需要有明确的关系(反映在图中，就是单向连通的关系，注意不能双向连通，那就成环了)。可见，全序就是偏序的一种特殊情况。
回到我们的选课例子中，如果机器学习需要在学习了计算机图形学之后才能学习(可能学的是图形学领域相关的机器学习算法……)，那么它们之间也就存在了确定的，原本的偏序关系就变成了全序关系。
实际上，很多地方都存在偏序和全序的概念。
比如对若干互不相等的整数进行排序，最后总是能够得到唯一的排序结果(从小到大，下同)。
这个结论应该不会有人表示疑问吧，但是如果我们以偏序/全序的角度来考虑一下这个再自然不过的问题，可能就会有别的体会了。 那么如何用偏序/全序来解释排序结果的唯一性呢？
我们知道不同整数之间的大小关系是确定的，即1总是小于4的，不会有人说1大于或者等于4吧。
这就是说，这序列是满足全序关系的。而对于拥有全序关系的结构(如拥有不同整数的数组)，在其线性化(排序)之后的结果必然是唯一的。
对于排序的算法，我们评价指标之一是看该排序算法是否稳定，即值相同的元素的排序结果是否和出现的顺序一致。
比如，我们说快速排序是不稳定的，这是因为最后的快排结果中相同元素的出现顺序和排序前不一致了。
如果用偏序的概念可以这样解释这一现象：相同值的元素之间的关系是无法确定的。因此它们在最终的结果中的出现顺序可以是任意的。
而对于诸如插入排序这种稳定性排序，它们对于值相同的元素，还有一个潜在的比较方式，即比较它们的出现顺序，出现靠前的元素大于出现后出现的元素。
因此通过这一潜在的比较，将偏序关系转换为了全序关系，从而保证了结果的唯一性。 拓展到拓扑排序中，结果具有唯一性的条件也是其所有顶点之间都具有全序关系。如果没有这一层全序关系，那么拓扑排序的结果也就不是唯一的了。
在后面会谈到，如果拓扑排序的结果唯一，那么该拓扑排序的结果同时也代表了一条哈密顿路径。
简单说就是，将有向图中的顶点以线性方式进行排序。即对于任何连接自顶点u到顶点v的有向边uv，在最后的排序结果中，顶点u总是在顶点v的前面。
抽象说：如果这个概念还略显抽象的话，那么不妨考虑一个非常非常经典的例子——选课。我想任何看过数据结构相关书籍的同学都知道它吧。
假设我非常想学习一门机器学习的课程，但是在修这么课程之前，我们必须要学习一些基础课程，比如计算机科学概论，C语言程序设计，数据结构，算法等等。
那么这个制定选修课程顺序的过程，实际上就是一个拓扑排序的过程，每门课程相当于有向图中的一个顶点，而连接顶点之间的有向边就是课程学习的先后关系。
只不过这个过程不是那么复杂，从而很自然的在我们的大脑中完成了。将这个过程以算法的形式描述出来的结果，就是拓扑排序。 那么是不是所有的有向图都能够被拓扑排序呢？显然不是。继续考虑上面的例子，如果告诉你在选修计算机科学概论这门课之前需要你先学习机器学习，你是不是会被弄糊涂？
在这种情况下，就无法进行拓扑排序，因为它中间存在互相依赖的关系，从而无法确定谁先谁后。在有向图中，这种情况被描述为存在环路。
因此，一个有向图能被拓扑排序的充要条件就是它是一个有向无环图
(DAG：Directed Acyclic Graph)。
简单说就是，将有向图中的顶点以线性方式进行排序。即对于任何连接自顶点u到顶点v的有向边uv，在最后的排序结果中，顶点u总是在顶点v的前面。
抽象说：如果这个概念还略显抽象的话，那么不妨考虑一个非常非常经典的例子——选课。我想任何看过数据结构相关书籍的同学都知道它吧。
假设我非常想学习一门机器学习的课程，但是在修这么课程之前，我们必须要学习一些基础课程，比如计算机科学概论，C语言程序设计，数据结构，算法等等。
那么这个制定选修课程顺序的过程，实际上就是一个拓扑排序的过程，每门课程相当于有向图中的一个顶点，而连接顶点之间的有向边就是课程学习的先后关系。
只不过这个过程不是那么复杂，从而很自然的在我们的大脑中完成了。将这个过程以算法的形式描述出来的结果，就是拓扑排序。 那么是不是所有的有向图都能够被拓扑排序呢？显然不是。继续考虑上面的例子，如果告诉你在选修计算机科学概论这门课之前需要你先学习机器学习，你是不是会被弄糊涂？
在这种情况下，就无法进行拓扑排序，因为它中间存在互相依赖的关系，从而无法确定谁先谁后。在有向图中，这种情况被描述为存在环路。
因此，一个有向图能被拓扑排序的充要条件就是它是一个有向无环图 (DAG：Directed Acyclic Graph)。
预备知识
一个较大的工程往往被划分成许多子工程，我们把这些子工程称作活动(activity)。
在整个工程中，有些子工程(活动)必须在其它有关子工程完成之后才能开始，也就是说，一个子工程的开始是以它的所有前序子工程的结束为先决条件的，但有些子工程没有先决条件，可以安排在任何时间开始。
为了形象地反映出整个工程中各个子工程(活动)之间的先后关系，可用一个有向图来表示，图中的顶点代表活动(子工程)，图中的有向边代表活动的先后关系，即有向边的起点的活动是终点活动的前序活动，只有当起点活动完成之后，其终点活动才能进行。
通常，我们把这种顶点表示活动、边表示活动间先后关系的有向图称做顶点活动网(Activity On Vertex network)，简称AOV网。
例如，假定一个计算机专业的学生必须完成图3-4所列出的全部课程。
在这里，课程代表活动，学习一门课程就表示进行一项活动，学习每门课程的先决条件是学完它的全部先修课程。
如学习《数据结构》课程就必须安排在学完它的两门先修课程《离散数学》和《算法语言》之后。
学习《高等数学》课程则可以随时安排，因为它是基础课程，没有先修课。若用AOV网来表示这种课程安排的先后关系，则如图3-5所示。
图中的每个顶点代表一门课程，每条有向边代表起点对应的课程是终点对应课程的先修课。图中的每个顶点代表一从图中可以清楚地看出各课程之间的先修和后续的关系。
如课程C5的先修课为C2，后续课程为C4和C6。
一个AOV网应该是一个有向无环图，即不应该带有回路，因为若带有回路，则回路上的所有活动都无法进行。
算法：
该算法的实现十分直观，关键在于需要维护一个入度为0的顶点的集合：
每次从该集合中取出(没有特殊的取出规则，随机取出也行，使用队列/栈也行，下同)一个顶点，将该顶点放入保存结果的List中。
紧接着循环遍历由该顶点引出的所有边，从图中移除这条边，同时获取该边的另外一个顶点，如果该顶点的入度在减去本条边之后为0，那么也将这个顶点放到入度为0的集合中。然后继续从集合中取出一个顶点………… 当集合为空之后，检查图中是否还存在任何边，如果存在的话，说明图中至少存在一条环路。不存在的话则返回结果List，此List中的顺序就是对图进行拓扑排序的结果。
public class KahnTopological
{
private List<Integer> result; // 用来存储结果集
private Queue<Integer> setOfZeroIndegree; // 用来存储入度为0的顶点
private int[] indegrees; // 记录每个顶点当前的入度
private int edges;
private Digraph di;
public KahnTopological(Digraph di)
{
this.di = di;
this.edges = di.getE();
this.indegrees = new int[di.getV()];
this.result = new ArrayList<Integer>();
this.setOfZeroIndegree = new LinkedList<Integer>();
// 对入度为0的集合进行初始化
Iterable<Integer>[] adjs = di.getAdj();
for(int i = 0; i < adjs.length; i++)
{
// 对每一条边 v -> w
for(int w : adjs[i])
{
indegrees[w]++;
}
}
for(int i = 0; i < indegrees.length; i++)
{
if(0 == indegrees[i])
{
setOfZeroIndegree.enqueue(i);
}
}
process();
}
private void process()
{
while(!setOfZeroIndegree.isEmpty())
{
int v = setOfZeroIndegree.dequeue();
// 将当前顶点添加到结果集中
result.add(v);
// 遍历由v引出的所有边
for(int w : di.adj(v))
{
// 将该边从图中移除，通过减少边的数量来表示
edges--;
if(0 == --indegrees[w]) // 如果入度为0，那么加入入度为0的集合
{
setOfZeroIndegree.enqueue(w);
}
}
}
// 如果此时图中还存在边，那么说明图中含有环路
if(0 != edges)
{
throw new IllegalArgumentException("Has Cycle !");
}
}
public Iterable<Integer> getResult()
{
return result;
}
}排序结果：
2->8->0->3->7->1->5->6->9->4->11->10->12
伪代码：
#include <bits/stdc++.h>
using namespace std;
int tp[10000],r[],c[];//r表示入度，c表示出度，tp表示最后生成的拓扑序
vector<int> G[];
void tuopu()
{
int cnt=0;
queue<int> q;
for(int i=1;i<=n;i++)
{
if(r[i]==0) q.push(i);
}
while(!q.empty())
{
int now=q.front();
q.pop();
tp[cnt++]=now;
for(int i=0;i<G[now].size();i++)
{
r[G[now][i]]--;
if(r[G[now][i]]==0) q.push(G[now][i]);
}
}
}
int main()
{
return 0;
}P1347 排序
/////////////代码来自 @李科良
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int n,m,num,sum,r[30],tmp[30];
char ans[30];
bool flag[30],f,l; // 记录那些点出现过
queue<int>q;
vector<int>v[30]; // 下标为元素 值为能到的元素
void topu(int x)
{
for(int i=1;i<=n;i++) tmp[i]=r[i];
while(!q.empty()) q.pop();
for(int i=1;i<=n;i++) if(r[i]==0) q.push(i),ans[++num]=(char)(i+64); // 找到一个起点 即最小的元素
if(num>1) return;
while(!q.empty())
{
int now=q.front(); // 此时的最小元素
q.pop();
for(int i=0;i<v[now].size();i++)
{
tmp[v[now][i]]--; // 这个元素能到的元素的入度减小
if(tmp[v[now][i]]==0) q.push(v[now][i]),ans[++num]=(char)(v[now][i]+64),sum++;
if(sum>1) {sum=0;return;}
if(num==n)
{
cout<<"Sorted sequence determined after "<<x<<" relations: ";
for(int k=1;k<=num;k++) cout<<ans[k];
cout<<".";
l=true;
return;
}
}
sum=0;
}
}
void dfs(int x,int i) // x是当前的起点 i是第几步询问
{
if(flag[x]) {cout<<"Inconsistency found after "<<i<<" relations.";f=true;return;}
flag[x]=true;
for(int j=0;j<v[x].size();j++)
{
dfs(v[x][j],i);
if(f) return;
}
flag[x]=false;
}
int main()
{
cin>>n>>m; // n个元素 m个关系
char a,b,c; // 将A B C ... 依次转换为 1 2 3 ...
for(int i=1;i<=m;i++)
{
cin>>a>>b>>c; // 表示 a<c 即a可以到c
r[c-64]++; // 入度增加 表示下标元素的入度
v[a-64].push_back(c-64); // 装下标可以到的元素
for(int j=1;j<=n;j++)
{
dfs(j,i);
if(f) return 0;
}
topu(i);
num=0;
if(l) return 0;
}
if(!l) cout<<"Sorted sequence cannot be determined.";
return 0;
}部分摘自 dm_vincent 的CSDN 博客 来自码云