{% blockquote 百度百科 <a href="http://baike.baidu.com/view/288212.htm">http://baike.baidu.com/view/288212.htm</a> 拓扑排序 %} 
对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边(u,v)∈E(G)，则u在线性序列中出现在v之前。 
通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。 
简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。 
{% endblockquote %}

 
举一个例子就是
> 学习《数据结构》前我们需要学习《C语言》 
> 学习《高数2》前我们需要学习《高数1》 
> 如何安排学习顺序？ 
我们有以下学习顺序：
<ul>
<li>《高数1》 -&gt; 《高数2》 -&gt; 《C语言》 -&gt; 《数据结构》</li>
<li>《高数1》 -&gt; 《C语言》 -&gt; 《数据结构》 -&gt; 《高数2》</li>
<li>《高数1》 -&gt; 《C语言》 -&gt; 《高数2》 -&gt; 《数据结构》</li>
<li>……</li>
</ul>
这种有着先行条件的排序就是拓扑排序。 
只有满足了先行条件，我们才能进行任务(到达结点) 
因此可以看作有向图 
同时，可以简单证明，如果存在环(<code>1-&gt;2</code>、<code>2-&gt;1</code>) 
显然是无解的。
对于拓扑排序，我们可以看成有向无环图(DAG)
<h1 id="heading">普通的拓扑排序</h1>
算法如下:
<ol>
<li>找出所有我们可以选择的结点(没有先行条件的结点(源))</li>
<li>选择一个源，开始拓展。对于每一个访问到的结点，从图中删除这个结点和这个结点指向的边(使以它为先行条件的结点变成源)</li>
<li>重复以上过程</li>
</ol>
如果所有源都访问过后，还有未访问的结点，那么存在环(因为环中的结点永远无法访问)
<h1 id="heading-1">带字典序的拓扑排序</h1>
题目:<a href="/post/HFUT/1359.html">&gt;吃在工大&lt;</a>
当输出要求输出字典序最大解时，我们可以维护一个优先队列，队首是字典序最大的元素。
将所有的源放在优先队列里，每次拓展结点从优先队列取出
代码如下
<pre style="background-color:#fff">bool G[maxn][maxn];
bool vis[maxn];
int n;

bool HasLoop() {
 //判断是否存在环
 for(int i = 1;i &lt;= n;i++)
 if(!vis[i])
 return false;
 return true;
}

bool IsStart(int k) {
 //判断是否入度为0
 for(int i = 1;i &lt;= n;i++)
 if(G[i][k])
 return false;
 return true;
}


bool TopoSort(int _n,int *ans) {
 //拓扑排序
 /*
 参数:
 邻接矩阵G[][]
 顶点数目n
 用于保存拓扑排序结果的数组 ans[]
 */
 //输出结果下标初始化
 int pos = 0;

 //已访问数组初始化
 memset(vis,false,sizeof(vis));

 //可被选择的数
 priority_queue&lt;int&gt; Q;

 //判断i是否为源
 for(int i = 1;i &lt;= n;i++) {
 if(IsStart(i))
 Q.push(i);
 }

 while(!Q.empty()) {
 int k = Q.top();
 Q.pop();

 if(vis[k])
 continue;
 else
 vis[k] = true;

 //记录到结果中
 ans[pos++] = k;

 for(int i = 1;i &lt;= n;i++) {
 if(G[k][i]) {
 //路径k~i存在
 //删除路径
 G[k][i] = false;
 //如果成为入度为0的点
 if(IsStart(i))
 Q.push(i);
 }
 }
 }

 //判断是否有环
 return HasLoop();
}
</pre>