aov数据结构算法

‘壹’ 数据结构，这个带权图的拓扑排序什么思路

由AOV网构造拓扑序列的拓扑排序算法主要是循环执行以下两步，直到不存在入度为0的顶点为止。
(1) 选择一个入度为0的顶点并输出之；
(2) 从网中删除此顶点及所有出边。

就是输出所有箭头都向外指的节点，然后删除与该节点相连的边，一直循环直到节点都输出或不能够找到这样的节点。
显然，拓扑排序不一定唯一。

题目的一种拓扑排序：
S,G,D,A,B,H,E,I,F,C,T

‘贰’ 求详解 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)。这个算法虽然简单，但是没有前面一个算法的效率高。

‘叁’ 求拓扑排序算法的详细讲解

3.1AOV网

在现代化管理中，人们常用有向图来描述和分析一项工程的计划和实施过程，一个工程常被分为多个小的子工程，这些子工程被称为活动（Activity)，在有向图中若以顶点表示活动，有向边表示活动之间的先后关系，这样的图简称为AOV网。如下图是计算机专业课程之间的先后关系：

基础知识课程应先于其它所有课程，pascal语言课程应先于数据结构。

3. 2 拓扑排序

在AOV网中为了更好地完成工程，必须满足活动之间先后关系，需要将各活动排一个先后次序即为拓扑排序。如上图的拓扑排序

基础知识；Pascal；数据结构；离散数学。或

基础知识；离散数学Pascal；数据结构。

拓扑排序的方法和步骤：

（1）在图中选一个没有前趋的顶点并输出之

（2）删除该顶点及由它发出的各边，直到图中不存在没有前趋的顶点为止。

若图中存在回路，拓扑排序无法进行。

以下是将一AOV网进行拓扑排序的算法：

网采用邻接矩阵A表示,若a[i，j]=1，表示活动i先于j，a[i，j]=0，表示活动i与j不存在先后关系。

（1）计算各顶点的入度

（2）找入度为零的点输出之，删除该点，且与该点关联各点的入度减1

（3）若所有顶点都输出完毕。

程序如下：

program tppv;
const maxn=100;
var
map:array[1..maxn,1..maxn] of byte;
into:array[1..maxn] of byte;
n,i,j,k:byte;
procere init;
var
i,j:integer;
begin
read(n);
for i:=1 to n do
for j:=1 to n do
begin
read(map[i,j]);
inc(into[j]);
end;
end;
begin
init;
for i:=1 to n do
begin
j:=1;
while (j<=n)and(into[j]<>0) do inc(j);
write(j,' ');
into[j]:=255;
for k:=1 to n do
if map[j,k]=1 then dec(into[k]);
end;
end.

3.3应用举例与练习

例：士兵排队问题：

有N个士兵（1<=N<=100),编号依次为1,2,...,N.队列训练时，指挥官要把士兵从高到矮排成一行，但指挥官只知道“1 比2 高，7 比 5高”这样的比较结果。

输入文件：第一行为数N（N〈=100）；表示士兵的个数。以下若干行每行两个数A，B 表示A高于B。

输出文件：给出一个合法的排队序列。

程序如下：

program tppv;
const maxn=100;
var
map:array[1..maxn,1..maxn] of byte;
into:array[1..maxn] of byte;
n,i,j,k:byte;
fp:text;
procere init;
var
i,j:integer;
begin
assign(fp,'tp.txt');
reset(fp);
readln(fp,n);
fillchar(map,sizeof(map),0);
fillchar(into,sizeof(into),0);
while not(seekeof(fp)) do
begin
readln(fp,i,j);
map[i,j]=1 ;
inc(into[j]);
end;
close(fp);
end;
begin
init;
for i:=1 to n do
begin
j:=1;
while (j<=n)and(into[j]<>0) do inc(j);
write(j,' ');
into[j]:=255;
for k:=1 to n do
if map[j,k]=1 then dec(into[k]);
end;
end.

练习：

Z语言问题：Z语言的基本字母也是26个，不妨用a到z表示，但先后顺序与英语不同。

现在按Z语言的顺序给出了N个单词，请依照这些单词给出一个可能的Z语言字母顺序。

输入文件：第一行一个数N（N<=100)表示单词的个数。

第二行到第N+1行，每行一个单词。

输出文件：仅一行，可能的字母顺序。

(图不好粘贴）

‘肆’ 数据结构用什么方法来判断有向图是否存在回路

数据结构中用拓扑排序来判断有向图是否存在回路。

用顶点表示活动、边表示活动间先后关系的有向图称做顶点活动网（AOV网）。一个AOV网应该是一个有向无环图，即不应该带有回路，因为若带有回路，则回路上的所有活动都无法进行。

在AOV网中，若不存在回路，则所有活动可排列成一个线性序列，使得每个活动的所有前驱活动都排在该活动的前面，数据结构中把此序列叫做拓扑序列，由AOV网构造拓扑序列的过程叫做拓扑排序。

综上，若一个有向图中存在拓扑排序，则有向图中不存在回路。

(4)aov数据结构算法扩展阅读：

在有向图进行拓扑排序的算法思想：

由AOV网构造拓扑序列的拓扑排序算法主要是循环执行以下两步，直到不存在入度为0的顶点为止。

1、选择一个入度为0的顶点并输出之；

2、从网中删除此顶点及所有出边。

循环结束后，若输出的顶点数小于网中的顶点数，则输出“有回路”信息，否则输出的顶点序列就是一种拓扑序列。

参考资料来源：网络-拓扑排序

参考资料来源：网络-有向图

‘伍’ 数据结构拓扑排序序列

对一个有向无环图简称G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边<u，v>∈E(G)，则u在线性序列中出现在v之前。通丛友常，这样的线性序列称为满足拓扑次序的序列，简称野友拓扑序列。

由拓扑序列的生成方法的出图中三种不同拓扑排序的序列：第一种：c1、c2、c4、c3、c5、c6，第二种：c1、c2、c4、c3、c6、c5，第三种：c1、c3、c2、c4、c5、c6。

循环结束后，若输出的顶点数小于网中的顶点数，则输出“有回路”信息，否则输出的顶点序列就是一种拓扑序列。

参考资料来源：网络-拓扑排序

‘陆’ 数据结构拓扑排序序列

拓扑排序序列有6种。先找到第一个没有被指的，就是C1，加入序列。然后擦掉跟C1有关的边，此时C2和C3都满足没有被指，选一个，比如选C2，加入序列，擦掉和C2有关的边，这个时候可以选C3,C4,C5或C6，如此而已。