一个数据结构的菜鸟问题

来源:百度知道 编辑:UC知道 时间:2024/06/01 04:22:33
数据结构中图的拓扑排序是怎么进行的请高手指导,最好能给些带有详细讲解的资料。谢谢

算法目的:试图得到一个有向无环图中的点的序列,使得每一个这个序列中处在后面的点,要么入度为0,要么可以由序列中前面的某个点走到,且不能由他出发走到序列中前面的某个点。
算法思想:
1.没有入度为0的而还有点没有进入队列,则无解,不存在拓扑序列。否则 2
2.将当前入度为0的点加入这个序列的尾部,将由他出发可以直接一步到达的那些点的入度减一。
3.如果所有点都已入队,则退出,否则 1

pascal代码:
procedure main;
var
change:boolean;
toposize,i,j:integer;
queue:array[1..maxn]of integer;
vis:array[1..maxn]of boolean;
begin
repeat
change:=false;
for i:=1 to n do
if not vis[i] and (d[i]=0) then
beign
inc(Toposize);
queue[toposize]:=i;
vis[i]:=true;
for j:=1 to n do
if g[i,j] then dec(d[j]);
change:=true;
end;
until not change;
if toposize<n then writlen('No Answer');
end;