数据结构--拓扑排序 AOV网_3.实现图的拓扑排序算法 描述 输出aov网(如下图)的拓扑排序序列,要求在同等条件

算法步骤：
1.从网中选取一个入度为0的顶点并且输出它
2.删除该顶点及其所有出边
3.重复1，2直到所有顶点已经输出，或者剩余顶点入度都不为0.说明网中存在回路无法继续进行拓扑排序。
代码：AOV网

void TopoOrder()
{
	int n=graphsize;
	int *count=new int[n];
	//caculate the count
	for (int i = 0;i < n;i++)
		count[i] = 0;
	// 记录各个结点的入度
	for (int i = 0;i < n;i++)
	{
		Edge *p = Head[i].adjacent;
		while (p!=NULL)
		{
			count[p->veradj]++;
			p = p->link;
		}
	}
	int top = -1;//初始化 栈顶指针
	for (int i = 0;i < n;i++)
	{
		if (count[i] == 0)//如果入度为0 入栈
		{
			count[i] = top;
			top = i;
		}
	}
	for (int i = 0;i < n;i++)//AOV网中最多有n个顶点
	{
		//若循环体尚未被执行n次，栈顶指针已经为-1 说明有回路，终止程序
		if (top == -1)
		{
			cout << "There is a cycle in network!" << endl;return;
		}
		else
		{
			int j = top;
			top = count[top];//从栈中弹出一个顶点
			cout << j << endl;//输出该顶点
			Edge* p = Head[j].adjacent;//令p为j的边链表指针
			while (p != NULL)
			{
				int k = p->veradj;
				//k的入度减一，若入度为0，则k入栈
				if (--count[k] == 0)
				{
					count[k] = top;
					top = k;
					p = p->link;
				}
			}
		}
	}
	delete[]count;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54