数据结构图 ------ 拓扑排序_数据结构如何写拓扑序列

一，拓扑排序的基本概念

拓扑排序听起来很抽象，但是其实并不难，拓扑排序主要分为2点。

• 首先将入度为0的顶点找到，然后作为一个排序目标排下去，
• 接着把自身顶点删掉，删掉的同时注意把相对应的弧或者边也删掉。
• 然后再找入度为0的顶点，然后…………………………

比如下图：

上面的拓扑排序就是 0 1 4 5 2 3 6。
下图，当出现两个顶点 1 和 4 的入度都为 0时候 ，其实两种都可以选择，所以拓扑排序的序列并不是唯一的。

二，拓扑排序的实现

有了对拓扑排序的理解，实现起来就很简单了。下面将会提到栈，但是都学到这里来了，栈要是不理解的话可以返回去看一下子。
第一步：建立一个栈，并把图中入度为0的点全部入栈。

 	int* stack = (int*)malloc(sizeof(int) * LG.vexnum);	
	
	//初始化栈	 将 图中入度为 0 的全部入栈 
	top = 0;
	for (i = 0; i < LG.vexnum; i++)
	{
		if(LG.adjlist[i].in == 0)
		{
			stack[++top] = i;
		} 
	}
1
2
3
4
5
6
7
8
9
10
11

第二步：出栈，然后将栈中所对应元素的入度删除
当你删除的过程中，如果删完之后发现它的入度已经为0了，那么直接将它入栈就好了。

	printf("拓扑排序结果如下：\n");
	//记录 
	count = 0;
	while( top != 0)
	{
		
		//出栈 
		gettop = stack[top--];
		printf("%d-> ",LG.adjlist[gettop].data);
		count++;
		
		//删除于刚出栈有关顶点的所有边 即入度
		ArcNode* cur = LG.adjlist[gettop].fristarc;
		while(cur != NULL)
		{
			LG.adjlist[cur->adjvex].in--;

			
			//如果在减完之后入度为 0 了 那么 直接入栈即可 
			if (LG.adjlist[cur->adjvex].in == 0)
			{
				stack[++top] = cur -> adjvex;
			}
			
			cur = cur -> next;
		}
		
	}
	printf("\n");
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

三，结尾

拓扑排序主要理解了它是如何进行排序的，实现不是问题。
要注意的是，如果此网的全部顶点都被输出，则证明此网不存在环，否则此网存在回路。
拓扑排序源码链接