拓扑排序序列（拓扑序列和逆拓扑序列的关系）

本文目录

• 拓扑序列和逆拓扑序列的关系
• 若有向图具有拓扑排序序列，那么它的邻接矩阵必定为
• 拓扑排序的流程图
• 数据结构 拓扑排序
• 拓扑排序
• 拓扑排序一定是三角矩阵吗
• 拓扑排序是怎么进行的

拓扑序列和逆拓扑序列的关系

一个拓扑排序倒着写的序列是逆拓扑排序
1、基于入度的算法，依次删去DAG中入度为0的结点输出，最终得到拓扑排序的序列。可以使用邻接表实现，时间复杂度O(V+E)。其中处理入度为0的结点可以采用栈或队列存储不影响（体现了拓扑的不唯一，基于BFS和DFS优先）
2、使用DFS递归的方式，本质是后序遍历，当完成邻接点的遍历，递归结束时输出该结点，此时得到的是逆拓扑排序，因此拓扑可以将他们用栈压入，最后再弹出就是拓扑排序。采用邻接表时间复杂度O(V+E)
3、基于出度的，依次删去DAG中出度为0的结点输出，得到逆拓扑排序，同上，可以使用栈实现拓扑排序。（一般都不会这么做，直接用入度的方式）。采用逆邻接表时间复杂度为O(V+E)。
拓扑排序比较简单，代码实现网上找找就有了，原理可以看看算法导论
拓扑排序主要用在1、检测有向图是否有环 2、实现DAG的O(V+E)的单源最短路径 3、应用在AOE中，求解关键路径

若有向图具有拓扑排序序列，那么它的邻接矩阵必定为

2-》3-》1这样顺序的图即可，直接就排除对称和三角了。

答案是三角。（这个三角不是特殊矩阵压缩存储时的三角矩阵，而是线性代数中的三角矩阵）

可以证明，对于有向图中顶点适当地编号，使其邻接矩阵为三角矩阵且主对角元全为零的充分必要条件是该有向图可以进行拓扑排序。

扩展资料：

给定有向图G=(VE)，并且给定该图G中的任意两个结点u和v，如果结点u与结点v相互可达，即至少存在一条路径可以由结点u开始，到结点v终止，同时存在至少有一条路径可以由结点v开始，到结点u终止，那么就称该有向图G是强连通图。

对于有向图最短路问题，计算步骤与求解无向图最短路问题相同，主要区别在于：无向图最短路问题使用单标号法。单标号法是对每一点赋予一个路权标号；而有向最短路问题使用双标号法．双标号法是对每一点赋予两个标号：路径和路权。

参考资料来源：百度百科-有向图

拓扑排序的流程图

由AOV网构造拓扑序列的拓扑排序算法主要是循环执行以下两步，直到不存在入度为0的顶点为止：选择一个入度为0的顶点并输出之；从网中删除此顶点及所有出边。

循环结束后，若输出的顶点数小于网中的顶点数，则输出“有回路”信息，否则输出的顶点序列就是一种拓扑序列。

由AOV网构造出拓扑序列的实际意义是：如果按照拓扑序列中的顶点次序，在开始每一项活动时，能够保证它的所有前驱活动都已完成，从而使整个工程顺序进行，不会出现冲突的情况。

扩展资料

拓扑排序（Topological Sorting）为一个有向无环图（DAG，Directed Acyclic Graph）的所有顶点的线性序列。且该序列必须满足下面两个条件：每个顶点出现且只出现一次。若存在一条从顶点A到顶点B的路径，那么在序列中顶点A出现在顶点B的前面。

拓扑排序常用来确定一个依赖关系集中，事物发生的顺序。例如，在日常工作中，可能会将项目拆分成A、B、C、D四个子部分来完成，但A依赖于B和D，C依赖于D。为了计算这个项目进行的顺序，可对这个关系集进行拓扑排序，得出一个线性的序列，则排在前面的任务就是需要先完成的任务。

参考资料来源：百度百科-拓扑序列

参考资料来源：百度百科-拓扑排序

数据结构 拓扑排序

【1】拓扑排序
在一个表示工程的有向图中，有顶点表示活动，用弧表示活动之间的优先关系，这样的有向图为顶点表示活动的网，我们称为AOV网。
AOV网中的弧表示活动之间存在的某种制约关系。
所谓拓扑排序，其实就是对一个有向图构造拓扑序列的过程。
【2】拓扑排序算法
对AOV网进行拓扑排序的基本思路：
从AOV网中选择一个入度为0的顶点输出；
然后删除此顶点，并删除以次顶点为尾的弧；
继续重复此操作.....
直到输出全部顶点或AOV网中不存在入度为0的顶点为止。
由于拓扑排序过程中，需要删除顶点，显然用邻接表更加方便。
因此我们需要为AOV网建立一个邻接表。
另外，考虑到算法过程中始终需要查找入度为0的顶点？
需要在原顶点表节点结构中，增加一个入度域in，in就是入度数字。

拓扑排序

　　1、堆栈

　　栈是一种特殊的线性表，插入或删除栈元素的运算只能在表的一端进行，称运算的一端为栈顶，另一端称为栈底。队列也是一种特殊的线性表（基本操作都是线性操作的子集）。

　　特点：后进先出

　　栈又称为“后进先出”的线性表，简称LIFO表。

　　栈的链式实现是以链表作为栈的存储结构，并在这种存储结构上实现栈的基本运算。栈的链式实现称为链栈。

　　2、有向无环图

　　描述含有公共子式的表达式的有效工具；

　　描述一项工程或系统的进行过程的有效工具。

　　3、一些概念

　　通常我们把计划、施工过程、生产流程、程序流程等都当成一个工程，一个大的工程常常被划分成许多较小的子工程，这些子工程称为活动。这些活动完成时，整个工程也就完成了。

　　我们用一种有向图来表示这些工程、计划等，在这种有向图中，顶点表示活动，有向边表示活动的优先关系，这种用顶点表示活动，用弧来表示活动间的优先关系的有向图叫做顶点表示活动的网络(Actire On Vertices)简称为AOV网。

　　拓扑排序：

　　假设G=(V，E)是一个具有n个顶点的有向图，V中顶点序列vl，v2，…，vn称做一个拓扑序列(TopologicalOrder)，当且仅当该顶点序列满足下列条件：若在有向图G中存在从顶点vi到vj的一条路径，则在顶点序列中顶点vi必须排在顶点vj之前。通常，在AOV网中，将所有活动排列成一个拓扑序列的过程叫做拓扑排序(Topological Sort)。

　　在AOV网中不应该出现有向环。因为环的存在意味着某项活动将以自己为先决条件，显然无法形成拓扑序列。

　　判定网中是否存在环的方法：对有向图构造其顶点的拓扑有序序列，若网中所有顶点都出现在它的拓扑有序序列中，则该AOV网中一定不存在环。

　　4、拓扑排序的算法思想

　　输入AOV网络。令 n 为顶点个数。

　　（1）在AOV网络中选一个没有直接前驱的顶点，并输出之；

　　（2）从图中删去该顶点, 同时删去所有它发出的有向边；

　　重复以上步骤，直到全部顶点均已输出，拓扑有序序列形成，拓扑排序完成；或图中还有未输出的顶点，但已跳出处理循环。这说明图中还剩下一些顶点，它们都有直接前驱，再也找不到没有前驱的顶点了。这时AOV网络中必定存在有向环。

　　5、拓扑排序算法的C语言描述

　　在实现拓扑排序的算法中，采用邻接表作为有向图的存储结构，每个顶点设置一个单链表，每个单链表有一个表头结点，在表头结点中增加一个存放顶点入度的域count，这些表头结点构成一个数组。

　　为了避免重复检测入度为0的点，另设一栈存放所有入度为0的点。

　　对于有n个顶点和e条边的有向图而言，for循环中建立入度为0的顶点栈时间为O（n）；若在拓扑排序过程中不出现有向环，则每个顶点出栈、入栈和入度减1的操作在while循环语句中均执行e次，因此拓扑排序总的时间花费为O (n+e)。

　　6、拓扑排序算法的C语言实现

　　#include“stdio.h“

　　#define MAX_VERTEX_NUM20

　　#include“conio.h“

　　#include“stdlib.h“

　　#define STACK_INIT_SIZE16

　　#define STACKINCREMENT5

　　typedef  int SElemType;

　　typedef charVertexType;

　　typedef struct

　　{

　　SElemType *base;

　　SElemType *top;

　　int stacksize;

　　}SqStack;

　　//我们依然用邻接表来作图的存储结构

　　typedef struct ArcNode{

　　int adjvex;

　　struct ArcNode *nextarc;

　　int info;

　　}ArcNode;  //表结点类型

　　typedef struct VNode{

　　VertexType data;

　　int count;

　　ArcNode *firstarc;

　　}VNode,AdjList[MAX_VERTEX_NUM];//头结点

　　typedef struct{

　　AdjList vertices;  //邻接表

　　int vexnum,arcnum;

　　}ALGraph;

　　int InitStack(SqStack&S)

　　{

　　S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));

　　if(!S.base) exit(-1);

　　S.top=S.base;

　　S.stacksize=STACK_INIT_SIZE;

　　return 1;

　　}//InitStack

　　int Push(SqStack&S,SElemType e)

　　{

　　if((S.top-S.base)》=S.stacksize)

　　{

　　S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType));

　　if(!S.base) exit(-1);

　　S.top=S.base+S.stacksize;

　　S.stacksize+=STACKINCREMENT;

　　}//if

　　*(S.top)=e;

　　S.top++;

　　return 1;

　　}//Push

　　int Pop(SqStack&S,SElemType &e)

　　{

　　if(S.top==S.base)return 0;

　　--S.top;

　　e=*S.top;

　　return 1;

　　}//Pop

　　int StackEmpty(SqStack&S)

　　{

　　if(S.top==S.base)return 1;

　　else return 0;

　　}//StackEmpty

　　int LocateVex(ALGraphG,char u)

　　{

　　int i;

　　for (i=0;i《G.vexnum;i++)

　　{ if(u==G.vertices[i].data) return i; }

　　if (i==G.vexnum) {printf(“Error u!\n“);exit(1);}

　　return 0;

　　}

　　voidCreateALGraph_adjlist(ALGraph &G)

　　{

　　int i,j,k,w;

　　char v1,v2,enter;

　　ArcNode *p;

　　printf(“Input vexnum &arcnum:\n“);

　　scanf(“%d“,&G.vexnum);

　　scanf(“%d“,&G.arcnum);

　　printf(“Input Vertices(以回车隔开各个数据):\n“);

　　for (i=0;i《G.vexnum;i++)

　　{     scanf(“%c%c“,&enter,&G.vertices[i].data);//注意点，解说

　　G.vertices[i].firstarc=NULL;

　　}//for

　　printf(“InputArcs(v1,v2,w)以回车分开各个数据:\n“);

　　for (k=0;k《G.arcnum;k++)

　　{

　　scanf(“%c%c“,&enter,&v1);

　　scanf(“%c%c“,&enter,&v2);

　　//scanf(“%d“,&w);

　　i=LocateVex(G,v1);

　　j=LocateVex(G,v2);

　　p=(ArcNode*)malloc(sizeof(ArcNode));

　　p-》adjvex=j;

　　//p-》info = w;

　　p-》nextarc=G.vertices[i].firstarc; //前插法,即每次都插入到头结点的后面

　　G.vertices[i].firstarc=p;

　　printf(“Next\n“);

　　}//for

　　return;

　　}//CreateALGraph_adjlist

　　voidFindInDegree(ALGraph &G)

　　{

　　int i,j;

　　for(i=0;i《G.vexnum;i++)

　　{

　　G.vertices[i].count=0;

　　}//for

　　for(j=0;j《G.vexnum;j++)

　　{

　　//G.vertices[i].count++;

　　for(ArcNode*p=G.vertices[j].firstarc;p;p=p-》nextarc)

　　G.vertices[p-》adjvex].count++;

　　}//for

　　}//FindInDegree

　　int TopoSort(ALGraph&G)

　　{

　　SqStack S;

　　FindInDegree(G);

　　InitStack(S);

　　for(inti=0;i《G.vexnum;i++)

　　if(G.vertices[i].count==0) Push(S,i);

　　int countt=0;

　　while(!StackEmpty(S))

　　{

　　int i,m;

　　m=Pop(S,i);

　　printf(“ %c“,G.vertices[i].data); ++countt;

　　for(ArcNode *p=G.vertices[i].firstarc;p;p=p-》nextarc)

　　{   int k;

　　k=p-》adjvex;

　　if(!(--G.vertices[k].count)) Push(S,k);

　　}//for

　　}//while

　　if(countt《G.vexnum) return 0;

　　else return 1;

　　}//TopoSort

　　int main()

　　{

　　ALGraph G;

　　CreateALGraph_adjlist(G);

　　TopoSort(G);

　　return 1;

　　}

　　7、malloc函数和realloc函数

　　realloc: void *realloc(void *block, size_t size)，将block所指存储块调整为大小size，返回新块的地址。如能满足要求，新块的内容与原块一致；不能满足要求时返回NULL，此时原块不变。

拓扑排序一定是三角矩阵吗

拓扑排序一定是三角矩阵。

上三角矩阵指的主对角线下方的元素全为零，而对角矩阵指的是主对角线上方与下方的元素都为零。所以对角阵一定是上三角阵，但上三角阵不一定是对角阵。

可以证明，对于有向图中顶点适当地编号，使其邻接矩阵为三角矩阵且主对角元全为零的充分必要条件是该有向图可以进行拓扑排序。

非计算机应用：

拓扑排序常用来确定一个依赖关系集中，事物发生的顺序。例如，在日常工作中，可能会将项目拆分成A、B、C、D四个子部分来完成，但A依赖于B和D，C依赖于D。为了计算这个项目进行的顺序，可对这个关系集进行拓扑排序，得出一个线性的序列，则排在前面的任务就是需要先完成的任务。

注意：这里得到的排序并不是唯一的！就好像你早上穿衣服可以先穿上衣也可以先穿裤子，只要里面的衣服在外面的衣服之前穿就行。

拓扑排序是怎么进行的

由AOV网构造拓扑序列的拓扑排序算法主要是循环执行以下两步，直到不存在入度为0的顶点为止。
(1)
选择一个入度为0的顶点并输出之；
(2)
从网中删除此顶点及所有出边。
循环结束后，若输出的顶点数小于网中的顶点数，则输出“有回路”信息，否则输出的顶点序列就是一种拓扑序列。