拓扑排序

B站小甲鱼视频
https://www.bilibili.com/video/BV1jW411K7yg?p=67
有向无环图（DAG）才有拓扑排序

拓扑序列：设G=(V,E)是一个具有n个顶点的有向图，V中的顶点序列V1,V2,……,Vn满足若从顶点Vi到Vj有一条路径，则在顶点序列中顶点Vi必在顶点Vj之前。则我们称这样的顶点序列为一个拓扑序列。
拓扑排序：所谓的拓扑排序，其实就是对一个有向图构造拓扑序列的过程。

• 对AOV网进行拓扑排序的方法和步骤如下：
– 从AOV网中选择一个没有前趋的顶点（该顶点的入度为0）并且输出它；
– 从网中删去该顶点，并且删去从该顶点发出的全部有向边；
– 重复上述两步，直到剩余网中不再存在没有前趋的顶点为止。

• 算法时间复杂度：
– 对一个具有n个顶点，e条边的网来说，初始建立入度为零的顶点栈，要检查所有顶点一次，执行时间为O(n)。
– 排序中，若AOV网无回路，则每个顶点入、出栈各一次，每个表结点被检查一次，因而执行时间是 O(n+e)。
– 所以，整个算法的时间复杂度是 O(n+e)。

// 边表结点声明
typedef struct EdgeNode
{
    
	int adjvex;
	struct EdgeNode *next;
}EdgeNode;

// 顶点表结点声明
typedef struct VertexNode
{
    
	int in;			// 顶点入度
	int data;
	EdgeNode *firstedge;
}VertexNode, AdjList[MAXVEX];

typedef struct
{
    
	AdjList adjList;
	int numVertexes, numEdges;
}graphAdjList, *GraphAdjList;

// 拓扑排序算法
// 若GL无回路，则输出拓扑排序序列并返回OK，否则返回ERROR
Status TopologicalSort(GraphAdjList GL)
{
    
	EdgeNode *e;
	int i, k, gettop;
	int top = 0;		// 用于栈指针下标索引
	int count = 0;		// 用于统计输出顶点的个数
	int *stack;			// 用于存储入度为0的顶点
	
	stack = (int *)malloc(GL->numVertexes * sizeof(int));
	
	for( i=0; i < GL->numVertexes; i++ )
	{
    
		if( 0 == GL->adjList[i].in )
		{
    
			stack[++top] = i;	// 将度为0的顶点下标入栈
		}
	}
	
	while( 0 != top )
	{
    
		gettop = stack[top--];	// 出栈
		printf("%d -> ", GL->adjList[gettop].data);
		count++;				
		
		for( e=GL->adjList[gettop].firstedge; e; e=e->next )
		{
    
			k = e->adjvex;
			// 注意：下边这个if条件是分析整个程序的要点！
			// 将k号顶点邻接点的入度-1，因为他的前驱已经消除
			// 接着判断-1后入度是否为0，如果为0则也入栈
			if( !(--GL->adjList[k].in) )	
			{
    
				stack[++top] = k;
			}
		}
	}
	
	if( count < GL->numVertexes )	// 如果count小于顶点数，说明存在环
	{
    
		return ERROR;
	}
	else
	{
    
		return OK;
	}
}