求这个图的拓扑排序算法的序列
点击联系发帖人
时间：2016-11-18 03:20
图的拓扑排序
转自：/xiaosuo/archive//1690302.html
对一个有向无环图(Directed Acyclic
Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若&u，v&
∈E(G)，则u在线性序列中出现在v之前。
&& 通常，这样的线性序列称为满足拓扑次序(TopoiSicai
Order)的序列，简称拓扑序列。
①若将图中顶点按拓扑次序排成一行，则图中所有的有向边均是从左指向右的。
②若图中存在有向环，则不可能使顶点满足拓扑次序。
③一个DAG的拓扑序列通常表示某种方案切实可行。
【例】一本书的作者将书本中的各章节学习作为顶点，各章节的先学后修关系作为边，构成一个有向图。按有向图的拓扑次序安排章节，才能保证读者在学习某章节时，其预备知识已在前面的章节里介绍过。
&& ④一个DAG可能有多个拓扑序列。
【例】对图G9进行拓扑排序，至少可得到如下的两个(实际远不止两个)拓扑序列：C0，C1，C2，C4，C3，C5，C7，C8，C6和C0，C7，C9，C1，C4，C2，C3，C6，C5。
⑤当有向图中存在有向环时，拓扑序列不存在
【例】下面(a)图中的有向环重排后如(b)所示，有向边&v3，vl&和其它边反向。若有向图被用来表示某项工程实施方案或某项工作计划，则找不到该图的拓扑序列(即含有向环)，就意味着该方案或计划是不可行的。
二、无前趋的顶点优先的拓扑排序方法
该方法的每一步总是输出当前无前趋(即人度为零)的顶点，其抽象算法可描述为：
NonPreFirstTopSort(G){//优先输出无前趋的顶点
& while(G中有人度为0的顶点)do{
从G中选择一个人度为0的顶点v且输出之；
&&&&& &
从G中删去v及其所有出边；
&&&&& &&
&&&& &&&
if(输出的顶点数目&|V(G)|)
&&&&& &&&&&
& //若此条件不成立，则表示所有顶点均已输出，排序成功。
&&&&&&& Error("G中存在有向环，排序失败！")；
&&&&
无前趋的顶点优先的拓扑排序算法在具体存储结构下，为便于考察每个顶点的人度，可保存各顶点当前的人度。为避免每次选入度为0的顶点时扫描整个存储空间，可设一个栈或队列暂存所有入度为零的顶点：
在开始排序前，扫描对应的存储空间，将人度为零的顶点均入栈(队)。以后每次选人度为零的顶点时，只需做出栈(队)操作即可。
三、无后继的顶点优先拓扑排序方法
1、思想方法&&&
该方法的每一步均是输出当前无后继(即出度为0)的顶点。对于一个DAG，按此方法输出的序列是逆拓扑次序。因此设置一个栈(或向量)T来保存输出的顶点序列，即可得到拓扑序列。若T是栈，则每当输出顶点时，只需做人栈操作，排序完成时将栈中顶点依次出栈即可得拓扑序列。若T是向量，则将输出的顶点从T[n-1]开始依次从后往前存放，即可保证T中存储的顶点是拓扑序列。
2、抽象算法描述
算法的抽象描述为：
NonSuccFirstTopSort(G){//优先输出无后继的顶点
while(G中有出度为0的顶点)do {
&&&&& &
从G中选一出度为0的顶点v且输出v；
&&&& &&
从G中删去v及v的所有人边
&&&& &&
if(输出的顶点数目&|V(G)|)
&&&&& &&&&&
Error("G中存在有向环，排序失败!")；
3、算法求精
在对该算法求精时，可用逆邻接表作为G的存储结构。设置一个向量outdegree[0..n-1]或在逆邻接表的顶点表结点中增加1个出度域来保存各
顶点当前的出度；设置一个栈或队列来暂存所有出度为零的顶点。除了增加一个栈或向量T来保存输出的顶点序列外，该算法完全类似于
NonPreFirstTopSort。
四、利用深度优先遍历对DAG拓扑排序
当从某顶点v出发的DFS搜索完成时，v的所有后继必定均已被访问过(想像它们均已被删除)，此时的v相当于是无后继的顶点，因此在DFS算法返回之前输出顶点v即可得到
DAG的逆拓扑序列。
其中第一个输出的顶点必是无后继(出度为0)的顶点，它应是拓扑序列的最后一个顶点。若希望得到的不是逆拓扑序列，同样可增加T来保存输出的顶点。若假设T是栈，并在DFSTraverse算法的开始处将T初始化，
&& 利用DFS求拓扑序列的抽象算法可描述为：
& void DFSTopSort(G，i，T){
//在DisTraverse中调用此算法，i是搜索的出发点，T是栈
&&& int
&&&
visited[i]=TRUE； //访问i
&&&
for(所有i的邻接点j)//即&i，j&∈E(G)
&&& &&
if(!visited[j])
&&&& &&
DFSTopSort(G，j，T)；
&&&& &&
//以上语句完全类似于DFS算法
&&&& &
Push(&T，i)； //从i出发的搜索已完成，输出i
&& & }
只要将深度优先遍历算法DFSTraverse中对DFS的调用改为对DFSTopSort的调用，即可求得拓扑序列T。其具体算法不难从上述抽象算法求精后得到。
若G是一个DAG，则用DFS遍历实现的拓扑排序与NonSuccFirstTopSort算法完全类似；但若C中存在有向环，则前者不能正常工作。
已投稿到：
以上网友发言只代表其个人观点，不代表新浪网的观点或立场。您所在位置： &
 &  & 
数据结构-后缀表式转树-图的拓扑排序-中缀式转树.doc13页
本文档一共被下载：
次 ,您可全文免费在线阅读后下载本文档。
文档加载中...广告还剩秒
需要金币：150 &&
数据结构-后缀表式转树-图的拓扑排序-中缀式转树
你可能关注的文档：
··········
··········
树和二叉树
1. 掌握二叉树，二叉树排序数的概念及存储方法。
2. 掌握二叉树的遍历算法。
3. 熟练掌握编写实现树的各种运算的算法。
4.熟悉图的各种存储方法。
5.掌握遍历图的递归和非递归的算法。
6. 理解图的有关算法。
1. 用二叉树表示代数表达式并输出代数表达式的前缀式和后缀式
编写一个程序，用二叉树来表示代数表达式，树的每个结点包括一个运算符，代数表达式由输入得到（其中只包含 ，+，-，*，/和用一个字母表示的数且没有错误，并且按照先乘除后加减的原则），试编写程序输出表达式的前缀式和后缀式。
2.求二叉树中从根结点到叶子节点的路径
对于1中的代数表达式二叉树，分别用递归和非递归的方法编写程序完成如下功能：
（1）.输出所有的叶子结点的数据项值。
（2）．输出所有从叶子节点到根结点的路径
3. 实现图的邻接矩阵和邻接表存储
对于下图所示的有向图G，编写一个程序完成如下功能：
（1 ． 建立G的邻接表存储结构
（2）． 输出下图的拓扑排序序列
（3）． 编写一个程序输出从顶点0开始的深度优先遍历序列（递归算法）和广度优先遍历序列（非递归算法）。
问题的表示方案
输入表达式构建huffman树之前需要将表达式转为后缀表达式然后二叉树进行构建。
主要数据类型与变量
//定义数据
typedef struct node
struct node*
struct node*
struct node*
BiTNode, *BinT//树/节点构造体
typedef struct EdgNode
struct EdgNode *L
;/*边构造体*/
typedef struct VertexNode
struct EdgNode *
;/*节点构造体*/
typedef struct ALGragh VertexNode VerticesList[20];
int numVertices, numE
正在加载中，请稍后...<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"
您的访问请求被拒绝 403 Forbidden - ITeye技术社区
您的访问请求被拒绝
亲爱的会员，您的IP地址所在网段被ITeye拒绝服务，这可能是以下两种情况导致：
一、您所在的网段内有网络爬虫大量抓取ITeye网页，为保证其他人流畅的访问ITeye，该网段被ITeye拒绝
二、您通过某个代理服务器访问ITeye网站，该代理服务器被网络爬虫利用，大量抓取ITeye网页
请您点击按钮解除封锁&以下试题来自：
单项选择题已知有向图G=(V，A)，其中V=a，b，c，d，e，A=＜a，b＞，＜a，c＞，＜d，c＞，＜d，e＞，＜b，e＞，＜c，e＞，对该图进行拓扑排序，下面序列中不是拓扑排序的是(
)。A．a，d，c，b，e B．d，a，b，c，e C．a，b，d，c，e D．a，b，c，d，e
为您推荐的考试题库
你可能感兴趣的试题
1A．故障中断 B．外部中断 C．不可屏蔽中断 D．访管中断2A．该进程本身 B．输入输出进程C．等待使用该临界区的进程 D．调度器进程3A．栈 B．队列 C．树 D．图4A．2G B．4G C．100K D．640K5A．3 B．2 C．3.4 D．2.4
热门相关试卷
最新相关试卷本周算法：图的拓扑排序 - ImportNew
假设我们有一组任务要完成，并且有些任务要在其它任务完成之后才能开始，所以我们必须非常小心这些任务的执行顺序。
如果这些任务的执行顺序足够简单的话，我们可以用链表来存储它们，这是一个很好的方案，让我们可以准确知道任务的执行顺序。问题是有时候不同任务之间的关系是非常复杂的，有些任务依赖于两个甚至更多的任务，或者反过来很多任务依赖自己。
因此我们不能通过链表或者树的数据结构来对这个问题建模。对这类问题唯一合理的数据结构就是图。我们需要哪种图呢？很显然，我们需要有向图来描述这种关系，而且是不能循环的有向图，我们称之为有向无环图。
要通过拓扑排序对图形进行排序，这些图必须是不能循环和有向的。
为什么这些图不能循环呢？答案很明显，如果图形是循环的，我们无法知道哪个任务该优先执行，也不可能对任务进行排序。
现在我们一要做的是对图中的每个节点排序，组成一条条边（u，v），u在v之前执行。然后我们就可以得到所有任务的线性顺序，并按这种顺序执行任务就一切都OK了。
拓扑排序的结果是节点的列表！这类排序称为“拓扑”排序（topsot）,它是非常基础的图形算法之一。
好的，现在我们有一个有向无环图，我们怎么遍历图的所有节点来得到排序后的链表呢？因为是一个无环图， 我们知道它一定有一个节点是没有依赖任务（一定要先执行的任务）的。所以我们可以把所有这类节点（没有依赖节点）先放进我们的链表。
第一步，我们就得到了所有没有依赖节点的节点了！
这个方法回答了我们的一个疑问：图形的拓扑图排序的正确结果是否不止一个呢？的确如此，我们只是把所有节点放到正确的顺序上，但是那些没有依赖节点的顺序都可以组合成一个正确的拓扑图排序结果。
我们从上面的图可以看到，即使是有依赖节点的节点的排序结果也可能有多种:[9, 6, 2, 7, 4, 1]是一个有效的有序拓扑图， [6, 9, 2, 7, 4, 1]也是如此。
现在我们可以得到这个算法的基本步骤：
1.构造空列表 L和S；
2.把所有没有依赖节点的节点放入L；
3.当L还有节点的时候，执行下面步骤：
3.1 L中拿出一个节点ｎ（从L中remove掉），并放入S
对每一个邻近n的节点m，
3.2.1 去掉边（n,m）;（表示加入最终结果集S）
3.2.2 如果m没有依赖节点，把m放入L;
上面这幅图描述了算法的 3.2
的执行过程。
下面算法非常简单的PHP语言的实现。你可以从这简短的代码中看到这个算法有多简单，而它对于计算机和编程的意义都是非常巨大的。
protected $_g = array(
array(0, 1, 1, 0, 0, 0, 0),
array(0, 0, 0, 1, 0, 0, 0),
array(0, 0, 0, 0, 1, 0, 0),
array(0, 0, 0, 0, 1, 0, 0),
array(0, 0, 0, 0, 0, 0, 1),
array(0, 0, 0, 0, 0, 0, 1),
array(0, 0, 0, 0, 0, 0, 0),
protected $_list = array();
protected $_ts
= array();
protected $_len
public function __construct()
$this-&_len = count($this-&_g);
// 找到没有依赖节点的节点
for ($i = 0; $i & $this-&_ $i++) {
for ($j = 0; $j & $this-&_ $j++) {
$sum += $this-&_g[$j][$i];
if (!$sum) {
//把它放入_list中
array_push($this-&_list, $i);
public function topologicalSort()
while ($this-&_list) {
$t = array_shift($this-&_list);
array_push($this-&_ts, $t);
foreach ($this-&_g[$t] as $key =& $vertex) {
if ($vertex == 1) {
$this-&_g[$t][$key] = 0;
for ($i = 0; $i & $this-&_ $i++) {
$sum += $this-&_g[$i][$key];
if (!$sum) {
array_push($this-&_list, $key);
print_r($this-&_ts);
正如我上面提到的，这个算法通常是用来确定相互依赖的任务的执行顺序的，当然不止这一个用处。实际上任何一种相互依赖的对象都可以用这种图形来建模。虽然有些时候这种图形是一种树，但大多数情况并不是这样。
原文链接：
- 译文链接： [ 转载请保留原文出处、译者和译文链接。]
关于作者：
（新浪微博：）
很明显前面几步都是多余的，应该直接从第6步开始
关于ImportNew
ImportNew 专注于 Java 技术分享。于日 11:11正式上线。是的，这是一个很特别的时刻 :)
ImportNew 由两个 Java 关键字 import 和 new 组成，意指：Java 开发者学习新知识的网站。 import 可认为是学习和吸收， new 则可认为是新知识、新技术圈子和新朋友……
新浪微博：
推荐微信号
反馈建议：@
广告与商务合作QQ：
– 好的话题、有启发的回复、值得信赖的圈子
– 写了文章？看干货？去头条！
– 为IT单身男女服务的征婚传播平台
– 优秀的工具资源导航
– 活跃 & 专业的翻译小组
– 国内外的精选博客文章
– UI,网页，交互和用户体验
– JavaScript, HTML5, CSS
– 专注Android技术分享
– 专注iOS技术分享
– 专注Java技术分享
– 专注Python技术分享
& 2016 ImportNew}
转自：/xiaosuo/archive//1690302.html
对一个有向无环图(Directed Acyclic
Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若&u，v&
∈E(G)，则u在线性序列中出现在v之前。
&& 通常，这样的线性序列称为满足拓扑次序(TopoiSicai
Order)的序列，简称拓扑序列。
①若将图中顶点按拓扑次序排成一行，则图中所有的有向边均是从左指向右的。
②若图中存在有向环，则不可能使顶点满足拓扑次序。
③一个DAG的拓扑序列通常表示某种方案切实可行。
【例】一本书的作者将书本中的各章节学习作为顶点，各章节的先学后修关系作为边，构成一个有向图。按有向图的拓扑次序安排章节，才能保证读者在学习某章节时，其预备知识已在前面的章节里介绍过。
&& ④一个DAG可能有多个拓扑序列。
【例】对图G9进行拓扑排序，至少可得到如下的两个(实际远不止两个)拓扑序列：C0，C1，C2，C4，C3，C5，C7，C8，C6和C0，C7，C9，C1，C4，C2，C3，C6，C5。
⑤当有向图中存在有向环时，拓扑序列不存在
【例】下面(a)图中的有向环重排后如(b)所示，有向边&v3，vl&和其它边反向。若有向图被用来表示某项工程实施方案或某项工作计划，则找不到该图的拓扑序列(即含有向环)，就意味着该方案或计划是不可行的。
二、无前趋的顶点优先的拓扑排序方法
该方法的每一步总是输出当前无前趋(即人度为零)的顶点，其抽象算法可描述为：
NonPreFirstTopSort(G){//优先输出无前趋的顶点
& while(G中有人度为0的顶点)do{
从G中选择一个人度为0的顶点v且输出之；
&&&&& &
从G中删去v及其所有出边；
&&&&& &&
&&&& &&&
if(输出的顶点数目&|V(G)|)
&&&&& &&&&&
& //若此条件不成立，则表示所有顶点均已输出，排序成功。
&&&&&&& Error("G中存在有向环，排序失败！")；
&&&&
无前趋的顶点优先的拓扑排序算法在具体存储结构下，为便于考察每个顶点的人度，可保存各顶点当前的人度。为避免每次选入度为0的顶点时扫描整个存储空间，可设一个栈或队列暂存所有入度为零的顶点：
在开始排序前，扫描对应的存储空间，将人度为零的顶点均入栈(队)。以后每次选人度为零的顶点时，只需做出栈(队)操作即可。
三、无后继的顶点优先拓扑排序方法
1、思想方法&&&
该方法的每一步均是输出当前无后继(即出度为0)的顶点。对于一个DAG，按此方法输出的序列是逆拓扑次序。因此设置一个栈(或向量)T来保存输出的顶点序列，即可得到拓扑序列。若T是栈，则每当输出顶点时，只需做人栈操作，排序完成时将栈中顶点依次出栈即可得拓扑序列。若T是向量，则将输出的顶点从T[n-1]开始依次从后往前存放，即可保证T中存储的顶点是拓扑序列。
2、抽象算法描述
算法的抽象描述为：
NonSuccFirstTopSort(G){//优先输出无后继的顶点
while(G中有出度为0的顶点)do {
&&&&& &
从G中选一出度为0的顶点v且输出v；
&&&& &&
从G中删去v及v的所有人边
&&&& &&
if(输出的顶点数目&|V(G)|)
&&&&& &&&&&
Error("G中存在有向环，排序失败!")；
3、算法求精
在对该算法求精时，可用逆邻接表作为G的存储结构。设置一个向量outdegree[0..n-1]或在逆邻接表的顶点表结点中增加1个出度域来保存各
顶点当前的出度；设置一个栈或队列来暂存所有出度为零的顶点。除了增加一个栈或向量T来保存输出的顶点序列外，该算法完全类似于
NonPreFirstTopSort。
四、利用深度优先遍历对DAG拓扑排序
当从某顶点v出发的DFS搜索完成时，v的所有后继必定均已被访问过(想像它们均已被删除)，此时的v相当于是无后继的顶点，因此在DFS算法返回之前输出顶点v即可得到
DAG的逆拓扑序列。
其中第一个输出的顶点必是无后继(出度为0)的顶点，它应是拓扑序列的最后一个顶点。若希望得到的不是逆拓扑序列，同样可增加T来保存输出的顶点。若假设T是栈，并在DFSTraverse算法的开始处将T初始化，
&& 利用DFS求拓扑序列的抽象算法可描述为：
& void DFSTopSort(G，i，T){
//在DisTraverse中调用此算法，i是搜索的出发点，T是栈
&&& int
&&&
visited[i]=TRUE； //访问i
&&&
for(所有i的邻接点j)//即&i，j&∈E(G)
&&& &&
if(!visited[j])
&&&& &&
DFSTopSort(G，j，T)；
&&&& &&
//以上语句完全类似于DFS算法
&&&& &
Push(&T，i)； //从i出发的搜索已完成，输出i
&& & }
只要将深度优先遍历算法DFSTraverse中对DFS的调用改为对DFSTopSort的调用，即可求得拓扑序列T。其具体算法不难从上述抽象算法求精后得到。
若G是一个DAG，则用DFS遍历实现的拓扑排序与NonSuccFirstTopSort算法完全类似；但若C中存在有向环，则前者不能正常工作。
已投稿到：
以上网友发言只代表其个人观点，不代表新浪网的观点或立场。您所在位置： &
 &  & 
数据结构-后缀表式转树-图的拓扑排序-中缀式转树.doc13页
本文档一共被下载：
次 ,您可全文免费在线阅读后下载本文档。
文档加载中...广告还剩秒
需要金币：150 &&
数据结构-后缀表式转树-图的拓扑排序-中缀式转树
你可能关注的文档：
··········
··········
树和二叉树
1. 掌握二叉树，二叉树排序数的概念及存储方法。
2. 掌握二叉树的遍历算法。
3. 熟练掌握编写实现树的各种运算的算法。
4.熟悉图的各种存储方法。
5.掌握遍历图的递归和非递归的算法。
6. 理解图的有关算法。
1. 用二叉树表示代数表达式并输出代数表达式的前缀式和后缀式
编写一个程序，用二叉树来表示代数表达式，树的每个结点包括一个运算符，代数表达式由输入得到（其中只包含 ，+，-，*，/和用一个字母表示的数且没有错误，并且按照先乘除后加减的原则），试编写程序输出表达式的前缀式和后缀式。
2.求二叉树中从根结点到叶子节点的路径
对于1中的代数表达式二叉树，分别用递归和非递归的方法编写程序完成如下功能：
（1）.输出所有的叶子结点的数据项值。
（2）．输出所有从叶子节点到根结点的路径
3. 实现图的邻接矩阵和邻接表存储
对于下图所示的有向图G，编写一个程序完成如下功能：
（1 ． 建立G的邻接表存储结构
（2）． 输出下图的拓扑排序序列
（3）． 编写一个程序输出从顶点0开始的深度优先遍历序列（递归算法）和广度优先遍历序列（非递归算法）。
问题的表示方案
输入表达式构建huffman树之前需要将表达式转为后缀表达式然后二叉树进行构建。
主要数据类型与变量
//定义数据
typedef struct node
struct node*
struct node*
struct node*
BiTNode, *BinT//树/节点构造体
typedef struct EdgNode
struct EdgNode *L
;/*边构造体*/
typedef struct VertexNode
struct EdgNode *
;/*节点构造体*/
typedef struct ALGragh VertexNode VerticesList[20];
int numVertices, numE
正在加载中，请稍后...<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"
您的访问请求被拒绝 403 Forbidden - ITeye技术社区
您的访问请求被拒绝
亲爱的会员，您的IP地址所在网段被ITeye拒绝服务，这可能是以下两种情况导致：
一、您所在的网段内有网络爬虫大量抓取ITeye网页，为保证其他人流畅的访问ITeye，该网段被ITeye拒绝
二、您通过某个代理服务器访问ITeye网站，该代理服务器被网络爬虫利用，大量抓取ITeye网页
请您点击按钮解除封锁&以下试题来自：
单项选择题已知有向图G=(V，A)，其中V=a，b，c，d，e，A=＜a，b＞，＜a，c＞，＜d，c＞，＜d，e＞，＜b，e＞，＜c，e＞，对该图进行拓扑排序，下面序列中不是拓扑排序的是(
)。A．a，d，c，b，e B．d，a，b，c，e C．a，b，d，c，e D．a，b，c，d，e
为您推荐的考试题库
你可能感兴趣的试题
1A．故障中断 B．外部中断 C．不可屏蔽中断 D．访管中断2A．该进程本身 B．输入输出进程C．等待使用该临界区的进程 D．调度器进程3A．栈 B．队列 C．树 D．图4A．2G B．4G C．100K D．640K5A．3 B．2 C．3.4 D．2.4
热门相关试卷
最新相关试卷本周算法：图的拓扑排序 - ImportNew
假设我们有一组任务要完成，并且有些任务要在其它任务完成之后才能开始，所以我们必须非常小心这些任务的执行顺序。
如果这些任务的执行顺序足够简单的话，我们可以用链表来存储它们，这是一个很好的方案，让我们可以准确知道任务的执行顺序。问题是有时候不同任务之间的关系是非常复杂的，有些任务依赖于两个甚至更多的任务，或者反过来很多任务依赖自己。
因此我们不能通过链表或者树的数据结构来对这个问题建模。对这类问题唯一合理的数据结构就是图。我们需要哪种图呢？很显然，我们需要有向图来描述这种关系，而且是不能循环的有向图，我们称之为有向无环图。
要通过拓扑排序对图形进行排序，这些图必须是不能循环和有向的。
为什么这些图不能循环呢？答案很明显，如果图形是循环的，我们无法知道哪个任务该优先执行，也不可能对任务进行排序。
现在我们一要做的是对图中的每个节点排序，组成一条条边（u，v），u在v之前执行。然后我们就可以得到所有任务的线性顺序，并按这种顺序执行任务就一切都OK了。
拓扑排序的结果是节点的列表！这类排序称为“拓扑”排序（topsot）,它是非常基础的图形算法之一。
好的，现在我们有一个有向无环图，我们怎么遍历图的所有节点来得到排序后的链表呢？因为是一个无环图， 我们知道它一定有一个节点是没有依赖任务（一定要先执行的任务）的。所以我们可以把所有这类节点（没有依赖节点）先放进我们的链表。
第一步，我们就得到了所有没有依赖节点的节点了！
这个方法回答了我们的一个疑问：图形的拓扑图排序的正确结果是否不止一个呢？的确如此，我们只是把所有节点放到正确的顺序上，但是那些没有依赖节点的顺序都可以组合成一个正确的拓扑图排序结果。
我们从上面的图可以看到，即使是有依赖节点的节点的排序结果也可能有多种:[9, 6, 2, 7, 4, 1]是一个有效的有序拓扑图， [6, 9, 2, 7, 4, 1]也是如此。
现在我们可以得到这个算法的基本步骤：
1.构造空列表 L和S；
2.把所有没有依赖节点的节点放入L；
3.当L还有节点的时候，执行下面步骤：
3.1 L中拿出一个节点ｎ（从L中remove掉），并放入S
对每一个邻近n的节点m，
3.2.1 去掉边（n,m）;（表示加入最终结果集S）
3.2.2 如果m没有依赖节点，把m放入L;
上面这幅图描述了算法的 3.2
的执行过程。
下面算法非常简单的PHP语言的实现。你可以从这简短的代码中看到这个算法有多简单，而它对于计算机和编程的意义都是非常巨大的。
protected $_g = array(
array(0, 1, 1, 0, 0, 0, 0),
array(0, 0, 0, 1, 0, 0, 0),
array(0, 0, 0, 0, 1, 0, 0),
array(0, 0, 0, 0, 1, 0, 0),
array(0, 0, 0, 0, 0, 0, 1),
array(0, 0, 0, 0, 0, 0, 1),
array(0, 0, 0, 0, 0, 0, 0),
protected $_list = array();
protected $_ts
= array();
protected $_len
public function __construct()
$this-&_len = count($this-&_g);
// 找到没有依赖节点的节点
for ($i = 0; $i & $this-&_ $i++) {
for ($j = 0; $j & $this-&_ $j++) {
$sum += $this-&_g[$j][$i];
if (!$sum) {
//把它放入_list中
array_push($this-&_list, $i);
public function topologicalSort()
while ($this-&_list) {
$t = array_shift($this-&_list);
array_push($this-&_ts, $t);
foreach ($this-&_g[$t] as $key =& $vertex) {
if ($vertex == 1) {
$this-&_g[$t][$key] = 0;
for ($i = 0; $i & $this-&_ $i++) {
$sum += $this-&_g[$i][$key];
if (!$sum) {
array_push($this-&_list, $key);
print_r($this-&_ts);
正如我上面提到的，这个算法通常是用来确定相互依赖的任务的执行顺序的，当然不止这一个用处。实际上任何一种相互依赖的对象都可以用这种图形来建模。虽然有些时候这种图形是一种树，但大多数情况并不是这样。
原文链接：
- 译文链接： [ 转载请保留原文出处、译者和译文链接。]
关于作者：
（新浪微博：）
很明显前面几步都是多余的，应该直接从第6步开始
关于ImportNew
ImportNew 专注于 Java 技术分享。于日 11:11正式上线。是的，这是一个很特别的时刻 :)
ImportNew 由两个 Java 关键字 import 和 new 组成，意指：Java 开发者学习新知识的网站。 import 可认为是学习和吸收， new 则可认为是新知识、新技术圈子和新朋友……
新浪微博：
推荐微信号
反馈建议：@
广告与商务合作QQ：
– 好的话题、有启发的回复、值得信赖的圈子
– 写了文章？看干货？去头条！
– 为IT单身男女服务的征婚传播平台
– 优秀的工具资源导航
– 活跃 & 专业的翻译小组
– 国内外的精选博客文章
– UI,网页，交互和用户体验
– JavaScript, HTML5, CSS
– 专注Android技术分享
– 专注iOS技术分享
– 专注Java技术分享
– 专注Python技术分享
& 2016 ImportNew}
我要回帖
更多关于 拓扑排序序列个数 的文章
更多推荐
- ·求解高考空间向量典型例题解析几何与向量代数的一道题目
- ·请问王者荣耀游戏代码这种结算界面需要代码制作吗？
- ·一个关于基础数列通项的例题的通项公式的题目？
- ·请问凯光的激光对抗系统单兵套装有哪些特点？
- ·toto马桶盖怎么拆捅怎样减少坑洞水位？
- ·史上最坑爹游戏10攻略的游戏4第七关怎么过 第七关攻略
- ·dnf一直卡在正在dnfpk一直连接服务器器怎么解决
- ·百度云电影分享 谢谢
- ·入手Q4p，有电流声，正常吗
- ·123507577谁的qq号?
- ·微信功能不能用
- ·经常听人说接口IP化，我想了解下到底指的是啥意思
- ·如何改变SecureCRT背景颜色
- ·郑州java学软件开发好找工作吗工作好找吗?
- ·e600f创维电视网卡如何安装
- ·棉被技术性能是什么意思
- ·求问 大家的推荐信都给出学生出国老师推荐信的真实EMAIL地址吗
- ·口袋助理移动办公app真的好用吗？我看到很多朋友的公司都在用
- ·服务器上不是oracle导出用户用户能导出吗
- ·固态硬盘和机械硬盘一起用需要怎么设置吗
- ·求这个图的拓扑排序算法的序列
- ·我在一个建网的网站，做了两个网站，完成后，他又向我要1000快的备案费用，备案难道不是
- ·密码中含有@符号怎么用sqlplus无法登录登录数据库
- ·悦动圈和苹果手机自带的微信排信排名不一致，是什么原因
- ·求死神动漫的百度云盘资源。 急 最好是高清的 急
- ·魅族mx6.屏幕亮度最高值多少.
- ·网络上那里买复合弓
- ·三星a7108跟a7100尾插排线区别通用吗
- ·现在手机和电脑一样都可以做淘宝刷单兼职吗
- ·索尼39h手机微信小符号在朋友圈显示不出来，像这种
- ·谁更好用 体验5款带wifi功能的wifi行车记录仪仪
- ·电脑开机键亮一下又灭了怎么回事
- ·windows开启ftp mac怎么用
- ·跪求青云志55-58百度云免费
- ·软件编程去沈阳就业好吗
- ·华为mate 9 pro 什么时候上市
