数据结构:利用函数实现图的拓扑排序（高分悬赏）

不会做

拓扑排序

一．定义

对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序(Topological Sort),是将G中所有顶点排成一个线性序列,使得对图中任意一对顶点u和v,若＜u,v＞∈E(G),则u在线性序列中出现在v之前。通常将这样的线性序列称为满足拓扑次序(Topolgical Order)的序列,简称拓扑序列。

二．算法

1.无前趋的顶点优先:

(1)算法描述：

(a)从网中选择一个入度为零的顶点输出；

(b)删除该顶点及其于该点有关的所有边；

(c)是否还有入度为零的顶点？若有，执行(a)，否则结束。

算法实现

以邻接表为图的存储结构的算法：

a)扫描顶点表，将入度为零的顶点入栈；

b)当栈非空时：

输出栈顶元素v，出栈；

检查v的出边，将每条出边的终端顶点的入度减1，若该顶点入度为0，入栈；

c)当栈空时，若输出的顶点小于顶点数，则说明AOV网有回路，否则拓扑排序完成。

算法实现：

void Graph::Toplogicasort()//top是入度为0的顶点栈的栈顶指针

{
int top=-1;
for(int i=0;i<n;i++) //建立如度为0顶点的链栈
if (count[i]==0)
{
count[i]=top;
top=i;
}
for(int i=0;i<n;i++)
if(top==-1)
{
cout<<"Network has a cycle"&l