算法总结2——拓扑排序

一.概念部分

1.拓扑排序介绍

��       将一个有向无环图(Directed Acyclic Graph简称DAG)进行排序进而得到一个有序的线性序列，就是拓扑排列。在C++语言中，我们可以使用邻接表来表示有向图。

       例如，一个项目包括A、B、C、D四个子部分来完成，并且A依赖于B和D，C依赖于D。现在要制定一个计划，写出A、B、C、D的执行顺序。这时，就可以利用到拓扑排序，它就是用来确定事物发生的顺序的。

2.有向无环图介绍

        一个较大的工程往往被划分成许多子工程，我们把这些子工程称作活动(activity)。在整个工程中，有些子工程(活动)必须在其它有关子工程完成之后才能开始，也就是说，一个子工程的开始是它的所有前序子工程的结束为先决条件的，但有些子工程没有先决条件，可以安排在任何时间开始。为了形象地反映出整个工程中各个子工程(活动)之间的先后关系，可用一个有向图来表示，图中的顶点代表活动(子工程)，图中的有向边代表活动的先后关系，即有向边的起点的活动是终点活动的前序活动，只有当起点活动完成之后，其终点活动才能进行。通常，我们把这种顶点表示活动、边表示活动间先后关系的有向图称做顶点活动网(Activity On Vertex network)，简称AOV网。一个AOV网就是一个有向无环图。

3.邻接表介绍

        邻接表是图的一种链式存储方法，其数据结构包括两部分：节点和邻接点。

（1）无向图的邻接表

图表如下：

解释：

• 节点V0的邻接点是节点V1，V2 ，V3，其邻接点的存储下标为1，2，3，按照头插法（逆序）将其放入节点V0后面的单链表中；

• 节点V1 的邻接点是节点V0 ，V2，其邻接点的存储下标为0，2，将其放入节点V1 后面的单链表中；

• 节点V2 的邻接点是节点V0，V1，V3，其邻接点的存储下标为0，1，3，将其放入节点V2 后面的单链表中；

• 节点V3 的邻接点是节点V0，V,2，其邻接点的存储下标为0，2，将其放入节点V3 后面的单链表中。

特点如下：

• 如果无向图有n 个节点、e 条边，则节点表有n 个节点，邻接点表有2e 个节点。

• 节点的度为该节点后面单链表中的节点数。

（2）有向图的邻接表（出弧）

图表如下：

   解释：

• 节点V0 的邻接点（只看出边，即出弧）是节点V3，其邻接点的存储下标为3，按照头插法（逆

序）将其放入节点V0 后面的单链表中；

• 节点V1 的邻接点是节点V0 ，V2，其邻接点的存储下标为0，2，将其放入节点V1后面的单链表中；

• 节点V2 的邻接点是节点V0，V1 ，其邻接点的存储下标为0，1，按头插法将其放入节点V0 后面的单链表中；

• 节点V3 没有邻接点，其后面的单链表为空。

特点如下：

• 如果有向图有n 个节点、e 条边，则节点表有n 个节点，邻接点表有e 个节点。

• 节点的出度为该节点后面单链表中的节点数。

（3）有向图的逆邻接表（入弧）

图表如下：

解释：

• 节点V0  的逆邻接点（只看入边，即入弧）是节点V1，V2，其邻接点的存储下标是1，2，其放入

节点V0 后面的单链表中；

• 节点V1  的逆邻接点是节点V2  ，其邻接点的存储下标为2，将其放入节点V1 后面的单链表中；

• 节点V2  的逆邻接点是V1，其邻接点的存储下标为1，按照头插法将其放入节点V2 后面的单链表中；

• 节点V3  的逆邻接点是节点V0  ，其邻接点的存储下标为0，将其放入节点V3 后面的单链表中；

特点如下：

• 如果有向图有n 个节点、e 条边，则节点表有n 个节点，邻接点表有e 个节点。

• 节点的入度为该节点后面的单链表中的节点数。

（4）邻接表的代码实现

//创建有向图的邻接表#include using namespace std;const int MaxVnum=100;//顶点数最大值 typedef char VexType;//顶点的数据类型为字符型typedef struct AdjNode{ //定义邻接点类型int v; //邻接点下标struct AdjNode *next; //指向下一个邻接点}AdjNode; typedef struct VexNode{ //定义顶点类型VexType data; // VexType为顶点的数据类型，根据需要定义AdjNode *first; //指向第一个邻接点}VexNode; typedef struct{//定义邻接表类型    VexNode  Vex[MaxVnum];    int vexnum,edgenum; //顶点数，边数}ALGragh; int locatevex(ALGragh G,VexType x){    for(int i=0;iv=j;    s->next=G.Vex[i].first;    G.Vex[i].first=s;} void printg(ALGragh G)//输出邻接表{   cout