数据结构-拓扑排序

介绍

介绍拓扑排序之前，首先要先引入一个名词，即AOV网：

• 如果有一项工程，它的完成需要多个活动组成，将活动看做结点，活动间的联系看做图的边，那么这样一个表示工程活动的有向图（活动存在制约关系，进行了一项才能进行下一项，所以是有向图），被称为AOV网

AOV网中不能存在回路，因为一个活动的开始需要其他活动的完成作为先决条件，但不能是活动本身导致了活动的开始。

拓扑序列的定义为：在一个AOV网中，如果从顶点i到顶点j之间有一条路径，则顶点序列中i必须在j之前。这样的顶点序列称为拓扑序列。

拓扑排序，就是将一个有向图构造成一个拓扑序列的过程。

构造时若此网的顶点可以被全部输出，则没有回路的存在，是AOV网；如果有顶点不能输出，则说明这个网存在回路，不是AOV网

具体实现

拓扑排序的基本思路为：不断从AOV网中选择一个入度为0的顶点，删除此顶点与其连接的边，直到输出全部顶点为止

（入度值，表示指向该顶点的边的数量，入度为0即没有任何边指向这个顶点）

具体步骤为：

1. 初始化一个队列，用来储存入度为0的顶点
2. 将所有入度为0的顶点入队
3. 依次取出入度为0的点，打印此顶点，对此顶点相连的边进行遍历
4. 将与其相连的顶点入度-1，如果为0则入队
5. 重复3,4，直到所有顶点都被输出

考虑到需要利用顶点的删除，相比于邻接矩阵，邻接表这种数据结构构成的图会更方便操作

在结构体中，需要有顶点域，入度值域与指向边表的指针

代码如下所示

typedef struct edge{
	int adjvex;//邻接点域，用于储存该顶点对应下标
	int info;//储存权值
	struct edge* next;//链域，指向下一个邻接点
}edge;
typedef struct vex{
	int v;//储存顶点
	int in;//记录入度；
	edge* first;//边表头指针
}vex,adjlist[MAX];
//储存邻接链表构成的网图信息
typedef struct{
	adjlist al;
	int numE,numN;
}graphAL;

拓扑排序过程如下

bool topo(graphAL g){
	int n=0;//记录输出的顶点值，判断是否为AOV网
	deque <int>q;//创建队列
	for (int i=0;i<g.numN;i++){
		if (g.al[i].in==0){//入度为0
			q.push_back(i);//入队
		}
	}
	while(!q.empty()){
		cout<<q.front()<<" ";//将入度为0的顶点输出
		n++;//输出的顶点数加1
		edge* e=g.al[q.front()].first;
		q.pop_front();//此顶点出队
		while(e){//处理其相邻顶点
			int temp=e->adjvex;//记录相邻顶点
            g.al[temp].in--;//入度减1
			if (g.al[temp].in==0)//入度为0则入队
			q.push_back(temp);
			e=e->next;//继续处理下一个相邻顶点
		}
	}
	if (n!=g.numN) return false;//输出的顶点数不对，则不是AOV图
	else return true;
}