㈠ 求详解 pascal 拓扑排序
拓扑排序
有向无回路图又称为dag。对这种有向无回路图的拓扑排序的结果为该图所有顶点的一个线性序列，满足如果G包含(u,v)，则在序列中u出现在v之前（如果图是有回路的就不可能存在这样的线性序列)。一个图的拓扑排序可以看成是图的所有顶点沿水平线排成的一个序列，使得所有的有向边均从左指向右。因此，拓扑排序不同于通常意义上对于线性表的排序。
有向无回路图经常用于说明事件发生的先后次序，图1给出一个实例说明早晨穿衣的过程。必须先穿某一衣物才能再穿其他衣物(如先穿袜子后穿鞋)，也有一些衣物可以按任意次序穿戴(如袜子和短裤)。图1(a)所示的图中的有向边(u,v)表明衣服u必须先于衣服v穿戴。因此该图的拓扑排序给出了一个穿衣的顺序。每个顶点旁标的是发现时刻与完成时刻。图1(b)说明对该图进行拓扑排序后将沿水平线方向形成一个顶点序列，使得图中所有有向边均从左指向右。
下列简单算法可以对一个有向无回路图进行拓扑排序。
procere Topological_Sort(G);
begin
1.调用DFS(G)计算每个顶点的完成时间f[v];
2.当每个顶点完成后，把它插入链表前端;
3.返回由顶点组成的链表;
end;
图1(b)说明经拓扑排序的结点以与其完成时刻相反的顺序出现。因为深度优先搜索的运行时间为θ(V+E)，每一个v中结点插入链表需占用的时间为θ(1)，因此进行拓扑排序的运行时间θ(V+E)。
图1 早晨穿衣的过程
为了证明算法的正确性，我们运用了下面有关有向无回路图的重要引理。
引理1
有向图G无回路当且仅当对G进行深度优先搜索没有得到反向边。
证明：
→：假设有一条反向边(u,v)，那么在深度优先森林中结点v必为结点u的祖先，因此G中从v到u必存在一通路，这一通路和边(u,v)构成一个回路。
←：假设G中包含一回路C，我们证明对G的深度优先搜索将产生一条反向边。设v是回路C中第一个被发现的结点且边(u,v)是C中的优先边，在时刻d[v]从v到u存在一条由白色结点组成的通路，根据白色路径定理可知在深度优先森林中结点u必是结点v的后裔，因而(u,v)是一条反向边。(证毕)
定理1
Topological_Sort(G)算法可产生有向无回路图G的拓扑排序。
证明:
假设对一已知有问无回路图G=(V,E)运行过程DFS以确定其结点的完成时刻。那么只要证明对任一对不同结点u,v∈V，若G中存在一条从u到v的有向边，则f[v]<f[u]即可。考虑过程DFS(G)所探寻的任何边(u,v)，当探寻到该边时，结点v不可能为灰色，否则v将成为u的祖先，(u,v)将是一条反向边，和引理1矛盾。因此，v必定是白色或黑色结点。若v是白色，它就成为u的后裔，因此f[v]<f[u]。若v是黑色，同样f[v]<f[u]。这样一来对于图中任意边(u,v)，都有f[v]<f[u]，从而定理得证。（证毕）
另一种拓扑排序的算法基于以下思想：首先选择一个无前驱的顶点（即入度为0的顶点，图中至少应有一个这样的顶点，否则肯定存在回路），然后从图中移去该顶点以及由他发出的所有有向边，如果图中还存在无前驱的顶点，则重复上述操作，直到操作无法进行。如果图不为空，说明图中存在回路，无法进行拓扑排序；否则移出的顶点的顺序就是对该图的一个拓扑排序。
下面是该算法的具体实现：
procere Topological_Sort_II(G);
begin
1 for 每个顶点u∈V[G] do d[u]←0; //初始化d[u],d[u]用来记录顶点u的入度
2 for 每个顶点u∈V[G] do
3 for 每个顶点v∈Adj[u] do d[v]←d[v]+1; //统计每个顶点的入度
4 CreateStack(s); //建立一个堆栈s
5 for 每个顶点u∈V[G] do
6 if d[u]=0 then push(u,s); //将度为0的顶点压入堆栈
7 count←0;
8 while (not Empty(s)) do
begin
9 u←top(s); //取出栈顶元素
10 pop(s); //弹出一个栈顶元素
11 count←count+1;
12 R[count]←u; //线性表R用来记录拓扑排序的结果
13 for 每个顶点v∈Adj[u] do //对于每个和u相邻的节点v
begin
14 d[v]←d[v]-1;
15 if d[v]=0 then push(v,s); //如果出现入度为0的顶点将其压入栈
end;
end;
16 if count<>G.size then writeln('Error! The graph has cycle.')
17 else 按次序输出R;
end;
上面的算法中利用d[u]来记录顶点u的入度，第2-3行用来统计所有顶点的入度，第5-6行将入度为0的顶点压入堆栈，第8-15行不断地从栈顶取出顶点，将该顶点输出到拓扑序列中，并将所有与该顶点相邻的顶点的入度减1，如果某个顶点的入度减至0，则压入堆栈，重复该过程直到堆栈空了为止。显而易见该算法的复杂度为O(VE)，因为第2-3行的复杂性就是O(VE)，后面8-15行的复杂性也是O(VE)。这个算法虽然简单，但是没有前面一个算法的效率高。
㈡ 高手解答 全拓扑排序 c语言算法 或者 算法思想也行啊
拓扑排序，很多时候，会作为算法的预处理。
它是针对有向无环图。
我空间中写过，比较详细。
算法思想：
针对一个有向无环图，求它的拓扑排序的一个简单方法：首先找到这个图中入度为0的顶点。把它放在序列的第一个位置，然后删除改顶点和它的边。得到一个新的有向无环图，在找这个图中入度为0的顶点。放在序列的下一个位置，然后再删除改顶点和它的边。。。，这个步骤重复直到图中所有的顶点都在序列中。
详细请看，有程序代码和相应的图片说明。
http://hi..com/huifeng00/blog/item/667348af89c42e044b36d6a6.html
㈢ 数据结构，这个带权图的拓扑排序什么思路
由AOV网构造拓扑序列的拓扑排序算法主要是循环执行以下两步，直到不存在入度为0的顶点为止。
(1) 选择一个入度为0的顶点并输出之；
(2) 从网中删除此顶点及所有出边。
就是输出所有箭头都向外指的节点，然后删除与该节点相连的边，一直循环直到节点都输出或不能够找到这样的节点。
显然，拓扑排序不一定唯一。
题目的一种拓扑排序：
S,G,D,A,B,H,E,I,F,C,T
㈣ 数据结构拓扑排序序列
拓扑排序序列有6种。先找到第一个没有被指的，就是C1，加入序列。然后擦掉跟C1有关的边，此时C2和C3都满足没有被指，选一个，比如选C2，加入序列，擦掉和C2有关的边，这个时候可以选C3,C4,C5或C6，如此而已。
㈤ 请解释下拓扑排序的定义。。和实现方法。。别复制百度百科。。
拓扑排序 所谓拓扑序列，就是有向图的最长路径问题，如果图中存在环，则最长路径是无法求得的，所以有拓扑序列的有向图不可以存在环。具体定义如下：
给出有向图G=（V，E），若结点的线形序列V1,V2,...Vn满足条件：对于i,j(1≤j<i≤n)，Vi和Vj之间没有边。求线形序列V1,V2,...Vn的过程就称为拓扑排序，这个线形序列就称为拓扑序列。
【拓扑排序主要思想】
有向图可以拓扑排序的条件是：图中没有环。
具体方法：
⑴ 从图中选择一个入度为0的点加入拓扑序列。
⑵ 从图中删除该结点以及它的所有出边（即与之相邻点入度减1）。
反复执行这两个步骤，直到所有结点都已经进入拓扑序列。
【实例：士兵排队问题】
有n个士兵(1≤n≤26)，依次编号为A,B,C,...，队列训练时，指挥官要把一些士兵从高到矮排成一行。但现在指挥官不能直接获得每个人的身高信息，只能获得逗p1比p2高地这样的比较结果，记作（p1>p2）。例如A>B，B>D，F>D，对应的排队方案有三个：AFBD，FABD，ABFD
【输入】
k行，每行a b，表示a>b
【输出】
一个可行的排队方案
【输入样例】
A B
B D
F D
【输出样例】
ABFD
㈥ 数据结构课设 题目：拓扑排序算法
//首先是用邻接表表视图,下面是邻接表的数据结构定义
const int MaxVertexNum = {图的最大顶点数，要大于等于具体图的顶点数n};
const int MaxEdgetNum = {图的最大边数，要大于等于具体图的边数e};
typedef VertexType vexlist[MaxVertexNum]; //定义vexlist为存储顶点信息的数组类型
struct edgenode //定义邻接表中的边结点类型
{
int adjvex; //邻接点域
int weight; //权值域
edgenode* next;//指向下一个边结点的链域
};
typedef edgenode* adjlist[MaxVertexNum]; //定义adjlist为存储n个表头指针的数组类型
//通过从键盘上输入的n个顶点信息和e条有向边信息建立顶点数组GV和邻接表GL
void Create2(vexlist GV, adjlist GL, int n, int e)
{
int i,j,k;
//建立顶点数组
cout<<"输入"<<n<<"个顶点的值："<<endl;
four(i = 0; i<n; i++)
cin>>GV[i];
//初始化邻接表
for(i=0; i<n; i++)
GL[i] = NULL;
//建立邻接表
cout<<"输入"<<e<<"条边："<<endl;
for(k=1; k<=e; k++)
{
//输入一条边<i,j>
cin>>i>>j;
//分配新结点
edgenode* p = new edgenode;
//将j值赋给新结点的邻接点域
p->adjvex = j;
//将新结点插入到邻接表表头
p->next = GL[i];
GL[i] = p;
}
}
//对邻接表GL表示的有n个顶点的有向图拓扑排序
void TopoSort(adjlist GL, int n)
{
int i,j,k,top,m=0; //m统计拓扑排序中的顶点数
edgenode* p;
//定义存储图中每个顶点入度的一维整型数组d
int* d = new int[n];
//初始化数组d中每个元素值为0
for(i=0; i<n; i++)
d[i] = 0;
//利用数组d记录每个顶点的入度
for(i = 0; i < n; i++)
{
p = GL[i];
while(p != NULL)
{
j = p->adjvex;
d[j]++;
p = p->next;
}
}
//初始化用于链接入度为0的栈顶指针top为-1
top = -1;
//建立初始栈
for(i = 0; i < n; i++)
if(d[i] == 0)
{
d[i] = top;
top = i;
}
//每循环一次删除一个顶点及所有出边
while(top != -1)
{
j = top; //j的值为一个入度为0的顶点序号
top = d[top]; //删除栈顶元素
cout<<j<<' '; //输出一个入度为0的顶点
m++; //输出顶点个数加1
p = GL[j]; //p指向邻接点表的第一个结点
while(p != NULL)
{
k = p->adjvex;
d[k]--;
if( d[k] == 0) //把入度为0的元素进栈
{
d[k] = top;
top = k;
}
p = p->next;
}
}
cout<<endl;
if(m<n)
cout<<"存在回路！"<<endl;
delete []d;
}