拓扑排序+关键路径

拓扑排序(Topological Sort)对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若<u，v> ∈E(G)，则u在线性序列中出现在v之前。通常，这样的线性序列称为满足拓扑次序(TopoiSicai Order)的序列，简称拓扑序列。注意：①若将图中顶点按拓扑次序排成一行，则图中所有的有向边均是从左指向右的。②若图中存在有向环，则不可能使顶点满足拓扑次序。③一个DAG的拓扑序列通常表示某种方案切实可行。【例】一本书的作者将书本中的各章节学习作为顶点，各章节的先学后修关系作为边，构成一个有向图。按有向图的拓扑次序安排章节，才能保证读者在学习某章节时，其预备知识已在前面的章节里介绍过。④一个DAG可能有多个拓扑序列。【例】对图G9进行拓扑排序，至少可得到如下的两个(实际远不止两个)拓扑序列：C0，C1，C2，C4，C3，C5，C7，C8，C6和C0，C7，C9，C1，C4，C2，C3，C6，C5。⑤当有向图中存在有向环时，拓扑序列不存在【例】下面(a)图中的有向环重排后如(b)所示，有向边<v3，vl>和其它边反向。若有向图被用来表示某项工程实施方案或某项工作计划，则找不到该图的拓扑序列(即含有向环)，就意味着该方案或计划是不可行的。无前趋的顶点优先的拓扑排序方法该方法的每一步总是输出当前无前趋(即人度为零)的顶点，其抽象算法可描述为：NonPreFirstTopSort(G){//优先输出无前趋的顶点while(G中有人度为0的顶点)do{从G中选择一个人度为0的顶点v且输出之；从G中删去v及其所有出边；}if(输出的顶点数目<|V(G)|)//若此条件不成立，则表示所有顶点均已输出，排序成功。Error("G中存在有向环，排序失败！")；}对G9执行上述算法的执行过程【参见动画演示】和得到的拓扑序列是C0，C1，C2，C4，C3，C5，C7，C9，C6。注意：无前趋的顶点优先的拓扑排序算法在具体存储结构下，为便于考察每个顶点的人度，可保存各顶点当前的人度。为避免每次选入度为0的顶点时扫描整个存储空间，可设一个栈或队列暂存所有入度为零的顶点：在开始排序前，扫描对应的存储空间，将人度为零的顶点均入栈(队)。以后每次选人度为零的顶点时，只需做出栈(队)操作即可。

拓扑排序（Topological Sorting） 拓扑排序（Topological Sorting）是一个有向无环图（DAG, Directed Acyclic Graph）的所有顶点的线性序列。 DAG的判定 拓扑排序的时间复杂度为O ( V + E ),因为DFS的时间复杂度度为O ( V + E ) 该序列必须满足下面两个条件： 它是一个 DAG 图，那么如何写出它的拓扑排序呢？这里说一种比较常用的方法： 重复 1 和 2 直到当前的 DAG 图为空或当前图中不存在无前驱的顶点为止。后一种情况说明有向图中必然存在环。 于是，得到拓扑排序后的结果是 { 1, 2, 4, 3, 5 }。 通常，一个有向无环图可以有一个或多个拓扑排序序列。 还有一种直观的方法是利用DFS,容易知道拓扑排序的序列为所有顶点的逆后续排列(ReversePostOrder)

广度优先搜索是最简单的图搜索算法之一。之所以得名是因为该算法始终将已经发现的结点集合，沿着其 广度方向 向外扩展去寻找未发现结点。 具体算法执行过程如下图所示： 深度优先搜索，只有可能就在图中尽可能的 深入 ，总是从最近才发现的结点出发，寻找下一个结点。 具体算法执行过程如下图所示： 拓扑排序是计算机中经常遇到的概念，下面用于《算法导论》的定义 如下图3-1所示，事件E1完成之后，可以同时执行事件E2和E3，两事件执行结束之后，执行事件E4，最后可以同时执行事件E5和E6。每个事件的执行都依赖于它之前事件是否执行完成，执行的顺序是固定的，这样的线性顺序就是 拓扑排序 。 图的广度、深度优先搜索和拓扑排序是图论算法中的基础，也是实践中经常遇到的问题。在考研和面试笔试中会通过选择题或者填空题考察，学习理解上文图示中的算法思想，辅助练习问题不大。当然也有关于这里的算法题，例如LeetCode815公交路线问题，就是利用图的广度优先搜索求解，因为解题复杂，并且在平时的应试中出现概率不大，这里不做详细讲解。有兴趣的可以在LeetCode中搜索，题目后面有我提交过的题解。

给定一个n个点m条边的有向图，点的编号是1到n，图中可能存在重边和自环。 请输出任意一个该有向图的拓扑序列，如果拓扑序列不存在，则输出-1。 若一个由图中所有点构成的序列A满足：对于图中的每条边(x, y)，x在A中都出现在y之前，则称A是该图的一个拓扑序列。 输入格式 第一行包含两个整数n和m 接下来m行，每行包含两个整数x和y，表示存在一条从点x到点y的有向边(x, y)。 输出格式 共一行，如果存在拓扑序列，则输出拓扑序列。 否则输出-1。 数据范围 1≤n,m≤105 拓扑排序：找到没有前驱的结点，删除。重复这个步骤。最后按照删除结点的顺序依次输出。 算法框架可以用宽搜，在宽搜框架中加入拓扑排序。

拓扑排序是有向图的一个重要操作。在给定的有向图G中，若顶点序列vi1,vi2,...,vin满足下列条件：若在有向图G中从顶点vi到顶点vj有一条路径，则在序列中顶点vi必在顶点vj之前，便称这个序列为一个拓扑序列。求一个有向图拓扑序列的过程称为拓扑排序。举例：计算机专业的学生应该学习的部分课程及其每门课程所需要的先修课程。拓扑排序的方法：（1）从图中选择一个入度为0的顶点且输出之；（2）从图中删掉该顶点及其所有以该顶点为弧尾的弧；反复执行这两个步骤，直到所有的顶点都被输出，输出的序列就是这个无环有向图的拓扑序列。细心的读者可能会发现：在每一时刻，可能同时存在多个入度为0的顶点，选择注：表中c1~c9列表示的是每个顶点的入度。下面我们讨论一下如何实现拓扑排序的算法。假设有向图以邻接表的形式存储。下面给出算法实现的基本过程：{ 将所有入度为0的顶点入栈；当栈非空时重复执行下列操作：从栈中退出顶点k；（1）将k顶点的信息输出；（2）将与k邻接的所有顶点的入度减1。 }#defineMAX_VERTEX_NUM30//最大顶点个数typestructEdgeLinklist{//边结点intadjvex;structEdgeLinklist*next;}EdgeLinklist;typedefstructVexLinklist{//顶点结点Elemtypeelem;intindegree;//记录顶点的入度EdgeLinklist*firstedge;}VexLinklist,AdjList[MAX_VERTEX_NUM];下面是拓扑排序的完整算法。 StatusTopologicalSort(AdjListadj){InitStack(s);for(i=0;i<MAX_VERTEX_NUM-1;i++)if(adj.indegree==0)Push(s,i);while(!StackEmpty(s)){Pop(s,i);printf(i);for(p=adj.firstedge;p;p=p->next){adj.indegree-=1;if(adj.indegree==0)Push(s,i);}

对有n个顶点和e条弧的有向图而言，建立求各顶点的入度的时间复杂度为O(e)；建零入度顶点栈的时间复杂度为O(n)；在拓扑排序过程中，若有向图无环，则每个顶点进一次栈、出一次栈，入度减1的操作在while语句中总共执行e次，所以总的时间复杂度为O(n+e)。对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边(u,v)∈E(G)，则u在线性序列中出现在v之前。通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。时间复杂度是同一问题可用不同算法解决，而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。计算机科学中，算法的时间复杂度是一个函数，它定性描述了该算法的运行时间。这是一个关于代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数。使用这种方式时，时间复杂度可被称为是渐近的，它考察当输入值大小趋近无穷时的情况。扩展资料在计算时间复杂度的时候，先找出算法的基本操作，然后根据相应的各语句确定它的执行次数，再找出 T(n) 的同数量级，找出后，f(n) = 该数量级，若 T(n)/f(n) 求极限可得到一常数c，则时间复杂度T(n) = O(f(n))。按数量级递增排列，常见的时间复杂度有：常数阶O(1),线性阶O(n),线性对数阶O(nlog2n),平方阶O(n^2)，立方阶O(n^3),...，k次方阶O(n^k),指数阶O(2^n)。随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。参考资料来源：百度百科-拓扑排序参考资料来源：百度百科-时间复杂度

拓扑排序一定是三角矩阵。上三角矩阵指的主对角线下方的元素全为零，而对角矩阵指的是主对角线上方与下方的元素都为零。所以对角阵一定是上三角阵，但上三角阵不一定是对角阵。可以证明，对于有向图中顶点适当地编号，使其邻接矩阵为三角矩阵且主对角元全为零的充分必要条件是该有向图可以进行拓扑排序。非计算机应用：拓扑排序常用来确定一个依赖关系集中，事物发生的顺序。例如，在日常工作中，可能会将项目拆分成A、B、C、D四个子部分来完成，但A依赖于B和D，C依赖于D。为了计算这个项目进行的顺序，可对这个关系集进行拓扑排序，得出一个线性的序列，则排在前面的任务就是需要先完成的任务。注意：这里得到的排序并不是唯一的！就好像你早上穿衣服可以先穿上衣也可以先穿裤子，只要里面的衣服在外面的衣服之前穿就行。

将入度为0的结点入队，删除后同时将所有相邻顶点的先决条件减一。当某个顶点的计数为0时，将它入队。这是关键思想。

终点序号从小到大的次序写拓扑排序是先后排序的意思。根据查询相关公开信息显示，终点序号从小到大的次序写拓扑排序一个不确定的偏序关系经全序后就有一种确定的先后顺序了，拓扑排序就是对有向无环图(DAG)上的一些点的编号进行排序，使得图中每条边的起点都比终点的位置要靠前。

实现的基本方法拓扑排序方法如下:(1)从有向图中选择一个没有前驱(即入度为0)的顶点并且输出它.(2)从网中删去该顶点,并且删去从该顶点发出的全部有向边.(3)重复上述两步,直到剩余的网中不再存在没有前驱的顶点为止.拓扑序列C++核心代码boolTopologicalSort(inta[][101])//可以完成拓扑排序则返回True{intn=a[0][0],i,j;intinto[101],ans[101];memset(into,0,sizeof(into));memset(ans,0,sizeof(ans));for(i=1;i<=n;i++){for(j=1;j<=n;j++){if(a[i][j]>0)into[j]++;}}into[0]=1;for(i=1;i<=n;i++){j=0;while(into[j]!=0){j++;if(j>n)returnfalse;}ans[i]=j;into[j]=-1;for(intk=1;k<=n;k++){if(a[j][k]>0)into[k]--;}}for(i=1;i<=n;i++){cout<<ans[i]<<"";}cout<<endl;returntrue;}

如图

有环有向图 在工程上是不可能实际存在的，因为不可能自己即是自己的先导又是自己的后驱 比如， 某学校规定，修完离散数学才能修数据结构，修完数据结构以后的下一门课程一定不是离散数学了。 这里的修完是指学完并考试通过，所以是重修的话还是进行不了下一道工序。 修完数据结构才能修离散，但修完理论就得修数据结构，这显然是一个死循环 所以有环有向图进行拓扑排序是一个伪概念，严蔚敏书上有讲的 假设你有这样一个环，那么理论是可能让你一直在这里环里面做死循环的。 [ ]

3.1AOV网 在现代化管理中，人们常用有向图来描述和分析一项工程的计划和实施过程，一个工程常被分为多个小的子工程，这些子工程被称为活动（Activity)，在有向图中若以顶点表示活动，有向边表示活动之间的先后关系，这样的图简称为AOV网。如下图是计算机专业课程之间的先后关系：基础知识课程应先于其它所有课程，pascal语言课程应先于数据结构。3. 2 拓扑排序 在AOV网中为了更好地完成工程，必须满足活动之间先后关系，需要将各活动排一个先后次序即为拓扑排序。如上图的拓扑排序基础知识；Pascal；数据结构；离散数学。或基础知识；离散数学Pascal；数据结构。拓扑排序的方法和步骤：（1）在图中选一个没有前趋的顶点并输出之（2）删除该顶点及由它发出的各边，直到图中不存在没有前趋的顶点为止。若图中存在回路，拓扑排序无法进行。以下是将一AOV网进行拓扑排序的算法：网采用邻接矩阵A表示,若a[i，j]=1，表示活动i先于j，a[i，j]=0，表示活动i与j不存在先后关系。（1）计算各顶点的入度 （2）找入度为零的点输出之，删除该点，且与该点关联各点的入度减1 （3）若所有顶点都输出完毕。 程序如下： program tppv;const maxn=100;var map:array[1..maxn,1..maxn] of byte; into:array[1..maxn] of byte; n,i,j,k:byte;procedure init;var i,j:integer;begin read(n); for i:=1 to n do for j:=1 to n do begin read(map[i,j]); inc(into[j]); end;end;begin init; for i:=1 to n do begin j:=1; while (j<=n)and(into[j]<>0) do inc(j); write(j," "); into[j]:=255; for k:=1 to n do if map[j,k]=1 then dec(into[k]); end;end. 3.3应用举例与练习 例：士兵排队问题： 有N个士兵（1<=N<=100),编号依次为1,2,...,N.队列训练时，指挥官要把士兵从高到矮排成一行，但指挥官只知道“1 比2 高，7 比 5高”这样的比较结果。输入文件：第一行为数N（N〈=100）；表示士兵的个数。以下若干行每行两个数A，B 表示A高于B。输出文件：给出一个合法的排队序列。程序如下：program tppv;const maxn=100;var map:array[1..maxn,1..maxn] of byte; into:array[1..maxn] of byte; n,i,j,k:byte; fp:text;procedure init;var i,j:integer;begin assign(fp,"tp.txt"); reset(fp); readln(fp,n); fillchar(map,sizeof(map),0); fillchar(into,sizeof(into),0); while not(seekeof(fp)) do begin readln(fp,i,j); map[i,j]=1 ; inc(into[j]); end; close(fp);end;begin init; for i:=1 to n do begin j:=1; while (j<=n)and(into[j]<>0) do inc(j); write(j," "); into[j]:=255; for k:=1 to n do if map[j,k]=1 then dec(into[k]); end;end.练习：Z语言问题：Z语言的基本字母也是26个，不妨用a到z表示，但先后顺序与英语不同。现在按Z语言的顺序给出了N个单词，请依照这些单词给出一个可能的Z语言字母顺序。输入文件：第一行一个数N（N<=100)表示单词的个数。 第二行到第N+1行，每行一个单词。输出文件：仅一行，可能的字母顺序。(图不好粘贴）

拓扑排序的核心就是每次找入度为0的点 进入输出队列 然后将与此点相连的节点入度减1 重复做当做n-1 次后还有点没进输出队列 那么这些点就是环上的 因为环上的各点入度都为1 没有0的 就不能更新

*/#include <stdio.h>#include <malloc.h>// 输出有向图的一个拓扑序列。实现算法7.12的程序 // 图的邻接表存储表示 #define MAX_NAME 3 // 顶点字符串的最大长度+1 #define MAX_VERTEX_NUM 20typedef int InfoType; // 存放网的权值 typedef char VertexType[MAX_NAME]; // 字符串类型 typedef enum{DG,DN,AG,AN}GraphKind; // {有向图,有向网,无向图,无向网} typedef struct ArcNode{ int adjvex; // 该弧所指向的顶点的位置 struct ArcNode *nextarc; // 指向下一条弧的指针 InfoType *info; // 网的权值指针） }ArcNode; // 表结点 typedef struct VNode{ VertexType data; // 顶点信息 ArcNode *firstarc; // 第一个表结点的地址,指向第一条依附该顶点的弧的指针 }VNode,AdjList[MAX_VERTEX_NUM];// 头结点 typedef struct{ AdjList vertices; int vexnum,arcnum; // 图的当前顶点数和弧数 int kind; // 图的种类标志 }ALGraph;// 若G中存在顶点u,则返回该顶点在图中位置;否则返回-1。 int LocateVex(ALGraph G,VertexType u){ int i; for(i=0;i<G.vexnum;++i) if(strcmp(u,G.vertices[i].data)==0) return i; return -1;}// 采用邻接表存储结构,构造没有相关信息的图G(用一个函数构造4种图)。int CreateGraph(ALGraph *G){ int i,j,k; int w; // 权值 VertexType va,vb; ArcNode *p; printf("请输入图的类型(有向图:0,有向网:1,无向图:2,无向网:3): "); scanf("%d",&(*G).kind); printf("请输入图的顶点数和边数:（空格） "); scanf("%d%d", &(*G).vexnum, &(*G).arcnum); printf("请输入%d个顶点的值(<%d个字符): ",(*G).vexnum,MAX_NAME); for(i = 0; i < (*G).vexnum; ++i) // 构造顶点向量 { scanf("%s", (*G).vertices[i].data); (*G).vertices[i].firstarc = NULL; } if((*G).kind == 1 || (*G).kind == 3) // 网 printf("请顺序输入每条弧(边)的权值、弧尾和弧头(以空格作为间隔): "); else // 图 printf("请顺序输入每条弧(边)的弧尾和弧头(以空格作为间隔): "); for(k = 0;k < (*G).arcnum; ++k) // 构造表结点链表 { if((*G).kind==1||(*G).kind==3) // 网 scanf("%d%s%s",&w,va,vb); else // 图 scanf("%s%s",va,vb); i = LocateVex(*G,va); // 弧尾 j = LocateVex(*G,vb); // 弧头 p = (ArcNode*)malloc(sizeof(ArcNode)); p->adjvex = j; if((*G).kind == 1 || (*G).kind == 3) // 网 { p->info = (int *)malloc(sizeof(int)); *(p->info) = w; } else p->info = NULL; // 图 p->nextarc = (*G).vertices[i].firstarc; // 插在表头 (*G).vertices[i].firstarc = p; if((*G).kind >= 2) // 无向图或网,产生第二个表结点 { p = (ArcNode*)malloc(sizeof(ArcNode)); p->adjvex = i; if((*G).kind == 3) // 无向网 { p->info = (int*)malloc(sizeof(int)); *(p->info) = w; } else p->info = NULL; // 无向图 p->nextarc = (*G).vertices[j].firstarc; // 插在表头 (*G).vertices[j].firstarc = p; } } return 1;}// 输出图的邻接表G。void Display(ALGraph G){ int i; ArcNode *p; switch(G.kind) { case DG: printf("有向图 "); break; case DN: printf("有向网 "); break; case AG: printf("无向图 "); break; case AN: printf("无向网 "); } printf("%d个顶点： ",G.vexnum); for(i = 0; i < G.vexnum; ++i) printf("%s ",G.vertices[i].data); printf(" %d条弧(边): ", G.arcnum); for(i = 0; i < G.vexnum; i++) { p = G.vertices[i].firstarc; while(p) { if(G.kind <= 1) // 有向 { printf("%s→%s ",G.vertices[i].data, G.vertices[p->adjvex].data); if(G.kind == DN) // 网 printf(":%d ", *(p->info)); } else // 无向(避免输出两次) { if(i < p->adjvex) { printf("%s－%s ",G.vertices[i].data, G.vertices[p->adjvex].data); if(G.kind == AN) // 网 printf(":%d ",*(p->info)); } } p=p->nextarc; } printf(" "); }}// 求顶点的入度，算法7.12、7.13调用void FindInDegree(ALGraph G,int indegree[]){ int i; ArcNode *p; for(i=0;i<G.vexnum;i++) indegree[i]=0; // 赋初值 for(i=0;i<G.vexnum;i++) { p=G.vertices[i].firstarc; while(p) { indegree[p->adjvex]++; p=p->nextarc; } }}typedef int SElemType; // 栈类型 #define STACK_INIT_SIZE 10 // 存储空间初始分配量 #define STACKINCREMENT 2 // 存储空间分配增量 // 栈的顺序存储表示 P46 typedef struct SqStack{ SElemType *base; // 在栈构造之前和销毁之后，base的值为NULL SElemType *top; // 栈顶指针 int stacksize; // 当前已分配的存储空间，以元素为单位 }SqStack; // 顺序栈// 构造一个空栈S。int InitStack(SqStack *S){ // 为栈底分配一个指定大小的存储空间 (*S).base = (SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if( !(*S).base ) exit(0); // 存储分配失败 (*S).top = (*S).base; // 栈底与栈顶相同表示一个空栈 (*S).stacksize = STACK_INIT_SIZE; return 1;}// 若栈S为空栈（栈顶与栈底相同的），则返回1，否则返回0。int StackEmpty(SqStack S){ if(S.top == S.base) return 1; else return 0;}// 插入元素e为新的栈顶元素。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(0); // 存储分配失败 (*S).top = (*S).base+(*S).stacksize; (*S).stacksize += STACKINCREMENT; } *((*S).top)++=e; // 这个等式的++ * 优先级相同，但是它们的运算方式，是自右向左 return 1;}// 若栈不空，则删除S的栈顶元素，用e返回其值，并返回1；否则返回0。int Pop(SqStack *S,SElemType *e){ if((*S).top == (*S).base) return 0; *e = *--(*S).top; // 这个等式的++ * 优先级相同，但是它们的运算方式，是自右向左 return 1;}// 算法7.12 P182// 有向图G采用邻接表存储结构。若G无回路,则输出G的顶点的一个拓扑序// 列并返回1, 否则返回0。int TopologicalSort(ALGraph G){ int i,k,count,indegree[MAX_VERTEX_NUM]; SqStack S; ArcNode *p; FindInDegree(G,indegree); // 对各顶点求入度indegree[0..vernum-1] InitStack(&S); // 初始化栈 for(i=0;i<G.vexnum;++i) // 建零入度顶点栈S if(!indegree[i]) Push(&S,i); // 入度为0者进栈 count=0; // 对输出顶点计数 while(!StackEmpty(S)) { // 栈不空 Pop(&S,&i); printf("%s ",G.vertices[i].data); // 输出i号顶点并计数 ++count; for(p=G.vertices[i].firstarc;p;p=p->nextarc) { // 对i号顶点的每个邻接点的入度减1 k=p->adjvex; if(!(--indegree[k])) // 若入度减为0,则入栈 Push(&S,k); } } if(count<G.vexnum) { printf("此有向图有回路 "); return 0; } else { printf("为一个拓扑序列。 "); return 1; }}int main(){ ALGraph f; printf("请选择有向图 "); CreateGraph(&f); Display(f); TopologicalSort(f); system("pause"); return 0; }/*输出效果：请选择有向图请输入图的类型(有向图:0,有向网:1,无向图:2,无向网:3): 0请输入图的顶点数和边数:（空格）4 4请输入4个顶点的值(<3个字符):abcd请顺序输入每条弧(边)的弧尾和弧头(以空格作为间隔):a ba cb dc d有向图4个顶点：a b c d4条弧(边):a→c a→bb→dc→da b c d 为一个拓扑序列。请按任意键继续. . . */

#include <cstdio>#include <cstring>#include <stack>using namespace std;///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// Description: 表示图的结点的邻接边struct Edge{ int dest; Edge *next;} **graph;///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// Description: 添加一个边// Input: e - 要添加边的结点, p - 目的地 // Output: e - 添加边后的结点void AddEdge(Edge *&e, int p){ if(!e) { e = new Edge; e->dest = p; e->next = 0; } else { Edge *tail = e; while (tail->next) tail = tail->next; tail->next = new Edge; tail = tail->next; tail->dest = p; tail->next = 0; }}///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// Description: 输入结点之间的边// Input: Console下用户输入,起点和终点; m - 边的个数// Output: graph - 图;void Input(int &m){ int i, a, b; // a->b存在边(有向) for (i = 0; i < m; i++) { scanf("%d %d", &a, &b); AddEdge(graph[a], b); }}///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// Description: 获得每个结点的入度// Input: n - 结点的个数// Output: degree - 每个结点的入度void GetDegree(int *degree, int n){ int i = 0; Edge *edge; memset(degree, 0, sizeof(int) * n); for (i = 0; i < n; i++) { edge = graph[i]; while(edge) { degree[edge->dest]++; edge = edge->next; } }}///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// Description: 拓扑排序// Input: n - 结点个数// Output: console下输出一个正确的拓扑序void TopoSort(int n){ int *degree = new int[n]; // 初始化所有结点的入度 GetDegree(degree, n); stack<int> s; // 获得入度为0的结点,并入栈 int i = 0; for (i = 0; i < n; i++) if (degree[i] == 0) s.push(i); int index = 0; // 结点的下标 Edge *edge; // 当前结点邻接表 while (!s.empty()) { index = s.top(); printf("%d", index); s.pop(); edge = graph[index]; while (edge) { if (--degree[edge->dest] == 0) s.push(edge->dest); edge = edge->next; } } delete []degree;}int main(){ int n, m; // 结点个数、边个数 scanf("%d %d", &n, &m); int i; graph = new Edge*[n]; for(i = 0; i < n; i++) graph[i] = 0; Input(m); TopoSort(n); return 0;}

伪代码：// 参数g为图，nodes为已经排序的顶点TopologicalSort(Graph g, List nodes) { g中所有没有前驱的顶点放入队列q; while(q不为空) { q中顶点出队，设为v; 复制nodes生成nodes的副本，并把v加入nodes的副本; 复制g生成g的副本，g的副本删去v和v发出的有向边; if (g的副本中没有顶点) { 输出nodes; // node为最终的排序 } else { TopologicalSort(g的副本, nodes的副本);//递归对剩下的图排序 } }}

拓扑排序是图论的基本算法之一;做一件事情，比如盖新房子，会分成很多工作:买地，买砖，打桩，砌砖，粉刷，放家具....但是这些工作是有一定顺序的，比如说不可能砖都没砌好就开始粉刷，盖房必须在买地买砖都完成后才能开始..所以对于一件事我们总要确定工作顺序，确定这个顺序的过程就是拓扑排序。算法思想是把整个事情看成一个有向无环图，每一个工作是一个点，如点A到B有弧则表示工作B必须在工作A之后完成。(1)将所有入度为0(即没有被任何工作限制的)节点放入堆栈S(2)堆栈中弹出一个节点,把有向图中这个点及它连接的所有边删除(3)跳到(1),直到有向图被全部删除出栈的序列就是所要求的拓扑序列.

AOV网络构造的拓扑序列的拓扑排序算法主要通过以下两个步骤循环，直到没有度为0的顶点，选择度为0的顶点，输出，从网络中删除这个顶点和所有向外的边。在循环结束时，如果输出的顶点数小于网络中的顶点数，则会输出“loop”信息，否则，输出顶点序列就是拓扑序列。利用AOV网络构建拓扑序列的实际意义是：如果按照拓扑序列的顶点顺序，在启动每个活动时，可以保证其所有前体活动都已完成，从而使整个项目有序进行，不会产生冲突。扩展资料：拓扑排序是一个DAG（有向无环图）的所有顶点的线性序列。序列必须满足以下两个条件：每个顶点只出现一次。如果从顶点A到顶点B有一条路径，那么在序列中顶点A出现在顶点B之前。拓扑排序通常用于确定事物在一组依赖项中发生的顺序。例如，在日常工作中，一个项目可能分为A，B，C和D，但取决于B和D和C取决于D计算项目的顺序，关系集可以拓扑排序产生一个线性序列，和第一个任务是需要首先完成。参考资料：百度百科-拓扑序列参考资料：百度百科-拓扑序列

有向图g可拓扑排序的判别条件是：每个顶点出现且只出现一次。判别，读音pàn bié，汉语词语，指根据不同点加以区分，辨别。根据不同点加以区分，辨别。示例：清·王夫之《姜斋诗话》卷二：“文章本静业，故曰‘仁者之言蔼如也"，学术风俗皆於此判别。”判，汉语常用字（一级字），会意兼形声字，最早见于战国文字。本义指分开、判分；由判分可引申为半、分辨、评断、判决义，用作半时“判”也可写作“牉”，以上义均读为pàn。“判”亦可表不顾、豁出去之义，这种意义上的“判”旧读为pān。判，会意兼形声字。从刀，从半，半亦表音。本义指分开、判分。《广雅·释诂一》：“判，分也。”《左传·庄公三年》：“纪于是乎始判。”杜预注：“判，分也。”由判分可引申为半、分辨、评断、判决义。用作半时，判也可写作“牉”。唐玄应《一切经音义》卷二：“判，古文胖，又作牉。”《周礼·地官·媒氏》：“掌万民之判。”郑玄注：“判，半也，得偶而合。”唐宋官制，以高官兼低职称判。元黄公绍《古今韵会举要·翰韵》：“宰相出典州曰判。”此用其假借义。以上义均读为pàn。

(1)设对有向无环图G=<V,E>，求得它的一个拓扑序列为S，过程如下: 初始化S为空，然后每次从G中选取一个入度为0的点v，将v插入到S的尾部，再在G中删除点v，并删除所有以v为弧尾的边(即由v引出去的边)，如此循环，直到图G中的V为空集时结束。21 2 3 4 5 6 7 81 3 2 4 5 7 6 83 1 4 2 5 6 7 83 1 2 5 4 7 8 6

冒泡排序是一种交换排序方式。设有n个数据依次放在数组元素a(1)至a(n)中，用冒泡法对这n个数据进行递增排序的过程为：先比较a(1)与a(2)，若逆序则交换之，接着比较a(2)与a(3)，若逆序就交换……依次进行，知道将a(n-1)与a(n)比较交换完，才算完成...

拓扑排序的方法是，先找到第一个没有被指的，就是C1，加入序列。然后擦掉跟C1有关的边，此时C2和C3都满足没有被指，选一个，比如选C2，加入序列，擦掉和C2有关的边，这个时候可以选C3,C4,C5或C6……如此而已

这道题选择B解题的步骤是根据边集画出图 这道题就四个结点 <1,2>表示有一条从结点1到结点2的有向路径，就是从1可以去2，但是不能从2到1.画的时候都遵循这个规律即可。然后是拓扑的规则首先找到一个只有出没有进的结点。你会发现只有结点1符合要求，那么去掉结点1和与结点1有关系的边，那么就剩下结点2、3、4.这个时候结点2、3没有进来的边，所以任选一个都可以。最后剩下结点四从2。就可以知道顺序了结点1是第一个 然后第二位2,3任选，但绝对不可能是4所以就选B。

由AOV网构造拓扑序列的拓扑排序算法主要是循环执行以下两步，直到不存在入度为0的顶点为止。(1) 选择一个入度为0的顶点并输出之；(2) 从网中删除此顶点及所有出边。就是输出所有箭头都向外指的节点，然后删除与该节点相连的边，一直循环直到节点都输出或不能够找到这样的节点。显然，拓扑排序不一定唯一。题目的一种拓扑排序：S,G,D,A,B,H,E,I,F,C,T

AOV网的拓扑排序序列BCADFE或BCAFDE

我知道你哪里不明白了，你没看见上面的for循环，1，如果不为0，则不执行if了，但执行for循环。2，执行for循环的目的就是把所有的入度减1，减为0的入栈。

显然不能。首先，拓扑排序是指对于一个有向无环图G，将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若<u，v> ∈E(G)，则u在线性序列中出现在v之前。那么，假设存在回路，v1,v2,v3,……,vn，v1，则边<v1,v2>∈E(G)，故v1在v2之前，类似地，v2在v3之前，……，因此，得出，v1在vn之前。又因为<vn,v1>∈E(G)，即vn在v1之前。相互矛盾，所以假设不成立。所以，一个图能够进行拓扑排序的一个必要条件就是图中不存在环。

那个选择题的答案错了，根据拓扑排序的原则，序列的第一个节点一定是没有前驱的，入度等于0的，不然怎么能够拓扑排序排在第一位呢，排在第一位也就是说没有任何前导的结点，入度一定为0了

O（n + e）。 对于一个具有n个顶点e条弧的有向图来说，刚开始将入度为0的顶点入栈的时间复杂为O(n)，在之后顶点出栈时，入度减1的操作共执行了e次，所以整个算法的时间复杂度为O(n + e)。

#include<stdio.h>#include<stdlib.h>#define Max_VertexNum 100 //顶点个数的宏定义/*邻接表结点*/typedef struct node{ int adjvex; /*邻接点域*/ struct node *next;/*链域*/}EdgeNode;/*顶点结点*/typedef struct vnode{ int vertex; //顶点域 int Degree; //存放入度 EdgeNode *firstedge; //边头指针}VertexNode;typedef VertexNode Adjlist[Max_VertexNum];//定义一个邻接表的数组,用于存放顶点的信息/*图的定义*/typedef struct ALGraph{ Adjlist adjlist; int n,e;//图的顶点和边}Graph;/*为了避免重复检测入度为0的顶点，设置一个栈暂存所有入度为0的顶点*/typedef struct stacknode{ int data; struct stacknode *next;}StackNode;typedef struct{ StackNode *top; //栈顶指针}LinkStack;////////////////////////////////////////////////////////////////////////////////////////////辅助栈的相关定义/*初始化栈*/void InitStack(LinkStack *S){ S->top=NULL;}/*判空*/int IsEmpty(LinkStack *S){ return(S->top==NULL);}/*进栈*/void Push(LinkStack *S,int x){ StackNode *p; p=(StackNode*)malloc(sizeof(StackNode)); p->data=x; p->next=S->top; S->top=p;}/*出栈*/int Pop(LinkStack *S){ int x; StackNode *p=S->top; //保存头指针 if(IsEmpty(S)) { printf("栈为空!"); exit(1); } x=p->data; S->top=p->next; //将栈顶结点从栈上摘下 free(p); return x;}/////////////////////////////////////////////////////////////////////////////////////////////////////*建立一个有向图，其存储结构为邻接表*/void CreateGraph(Graph *G){ int i,j,k; EdgeNode *s; printf("请输入图的顶点数和边数: "); scanf("%d %d",&G->n,&G->e); //建立顶点列表 for(i=1;i<=G->n;i++) { printf("请输入顶点的信息: "); printf(" "); scanf("%d",&G->adjlist[i].vertex); G->adjlist[i].firstedge=NULL; } for(k=0;k<G->e;k++) { printf("请输入边(vi,vj)的顶点序号: "); printf(" "); scanf("%d%d",&i,&j); s=(EdgeNode*)malloc(sizeof(EdgeNode)); //生成边表结点 s->adjvex=j; s->next=G->adjlist[i].firstedge; G->adjlist[i].firstedge=s; //将新建的结点插入到边表的头部 }}//////////////////////////////////////////////////////////////////////////////////////////////////////////*对各个顶点求入度*/void FindInDegree(Graph *G){ int i,j; EdgeNode *p; for(i=1;i<=G->n;i++) { G->adjlist[i].Degree=0; } for(j=1;j<=G->n;j++) { for(p=G->adjlist[j].firstedge;p;p=p->next) { G->adjlist[p->adjvex].Degree++; } /* p=G->adjlist[j].firstedge; while(p!=NULL) { G->adjlist[p->adjvex].Degree++; p=p->next; } */ }}////////////////////////////////////////////////////////////////////////////////////////////////////////////////*进行拓扑有序排列*/int TopoSort(Graph *G){ int i,m,k; int count=0; LinkStack S; FindInDegree(G); InitStack(&S); for(i=1;i<=G->n;i++) { if(!G->adjlist[i].Degree) { Push(&S,i); } } while(!IsEmpty(&S)) { m=Pop(&S); printf("(%d,%d)",m,G->adjlist[m].vertex); //输出i号顶点并计数 count++; for(EdgeNode *p=G->adjlist[m].firstedge;p;p= p->next) { k=p->adjvex; if(!(--G->adjlist[k].Degree)) { Push(&S,k); } } } if(count<G->n) { printf("有回路!"); exit(1); } else { return 0; }}/////////////////////////////////////////////////////////////////////////////////////////////////////////////*输出有向图*/void PrintAdjlist(Graph *G){ int i; EdgeNode *p; for(i=1;i<=G->n;i++) { printf("%d:%d",i,G->adjlist[i].vertex); for(p=G->adjlist[i].firstedge;p;p=p->next) { printf("%d",p->adjvex); } printf(" "); } }///////////////////////////////////////////////////////////////////////////////////////////////////////////////////*主函数*/void main(){Graph G;CreateGraph(&G);PrintAdjlist(&G);TopoSort(&G);}

1、从有向图中选择一个出度为0的顶点输出2、删除1中的顶点，并且删除指向该顶点的全部边3、重复上述两步，直到剩余的图中不存在出度为0的顶点为止如上，得到的序列为逆拓扑序列

lint topsort( ALGraph *G) /*拓扑排序*/{ int i,j,k,top =-1; EdgeNode *ptr; for(i=0;i<G->n;i++) /*入度为0入栈*/ { if(G->adjlist[i].indegree==0) { G->adjlist[i].indegree=top; top=i; } } {if(top==-1) return -1; /*网中有回路*/ j=top;for(i=0;i<G->n;i++) { if(top==-1) return -1;/*AOV网中有回路*/ j=top; top=G->adjlist[top].indegree; /*从栈中退出一个入度为0的顶点并输出*/ printf("->%s",G->adjlist[j].vertex); ptr=G->adjlist[j].firstedge; { k=ptr->adjvex; G->adjlist[k].indegree--; /*修改其他顶点的入度*/ if(G->adjlist[k].indegree==0) /*为0入栈*/ while(ptr!=NULL) { G->adjlist[k].indegree=top; top=k; } ptr=ptr->next; } }}

首先排序对于计算机处理数据是非常重要。拓扑排序是一种方法，如果你学过数据结构的话，在讲图这种数据结构的时候就会涉及，它主要是判断一个有向图是否存在回路，为求有向图的最长路径。

虽然题目里给出了拓扑排序这样的提示，但我还是难想到与拓扑排序有关的解决方法T^T。不过我脑子里有另外一个算法，不知道对不对：给ans数组赋初值:ans[i]=i;枚举每对交叉，将交叉中编号较大的导线的ans值-1，反之将交叉中编号较小的导线的ans值+1按照ans数组的大小，将对应的 i 输出.

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

由AOV网构造拓扑序列的拓扑排序算法主要是循环执行以下两步，直到不存在入度为0的顶点为止：选择一个入度为0的顶点并输出之；从网中删除此顶点及所有出边。循环结束后，若输出的顶点数小于网中的顶点数，则输出“有回路”信息，否则输出的顶点序列就是一种拓扑序列。由AOV网构造出拓扑序列的实际意义是：如果按照拓扑序列中的顶点次序，在开始每一项活动时，能够保证它的所有前驱活动都已完成，从而使整个工程顺序进行，不会出现冲突的情况。扩展资料拓扑排序（Topological Sorting）为一个有向无环图（DAG，Directed Acyclic Graph）的所有顶点的线性序列。且该序列必须满足下面两个条件：每个顶点出现且只出现一次。若存在一条从顶点A到顶点B的路径，那么在序列中顶点A出现在顶点B的前面。拓扑排序常用来确定一个依赖关系集中，事物发生的顺序。例如，在日常工作中，可能会将项目拆分成A、B、C、D四个子部分来完成，但A依赖于B和D，C依赖于D。为了计算这个项目进行的顺序，可对这个关系集进行拓扑排序，得出一个线性的序列，则排在前面的任务就是需要先完成的任务。参考资料来源：百度百科-拓扑序列参考资料来源：百度百科-拓扑排序

拓扑排序的方法是，先找到第一个没有被指的，就是C1，加入序列。然后擦掉跟C1有关的边，此时C2和C3都满足没有被指，选一个，比如选C2，加入序列，擦掉和C2有关的边，这个时候可以选C3,C4,C5或C6……如此而已

拓扑排序 所谓拓扑序列，就是有向图的最长路径问题，如果图中存在环，则最长路径是无法求得的，所以有拓扑序列的有向图不可以存在环。具体定义如下： 给出有向图G=（V，E），若结点的线形序列V1,V2,...Vn满足条件：对于i,j(1≤j<i≤n)，Vi和Vj之间没有边。求线形序列V1,V2,...Vn的过程就称为拓扑排序，这个线形序列就称为拓扑序列。【拓扑排序主要思想】 有向图可以拓扑排序的条件是：图中没有环。 具体方法： ⑴ 从图中选择一个入度为0的点加入拓扑序列。 ⑵ 从图中删除该结点以及它的所有出边（即与之相邻点入度减1）。 反复执行这两个步骤，直到所有结点都已经进入拓扑序列。【实例：士兵排队问题】有n个士兵(1≤n≤26)，依次编号为A,B,C,...，队列训练时，指挥官要把一些士兵从高到矮排成一行。但现在指挥官不能直接获得每个人的身高信息，只能获得“p1比p2高”这样的比较结果，记作（p1>p2）。例如A>B，B>D，F>D，对应的排队方案有三个：AFBD，FABD，ABFD【输入】 k行，每行a b，表示a>b【输出】 一个可行的排队方案【输入样例】A BB DF D　　【输出样例】ABFD

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

对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若<u，v> ∈E(G)，则u在线性序列中出现在v之前。拓扑排序(Topological Sort)什么是拓扑序列 通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。离散数学中关于偏序和全序的定义： 若集合X上的关系是R是自反的、反对称的和传递的，则称R是集合X上的偏序关系。 设R是集合X上的偏序（Partial Order）,如果对每个x,y属于X必有xRy 或 yRx，则称R是集合X上的全序关系。 注意： ①若将图中顶点按拓扑次序排成一行，则图中所有的有向边均是从左指向右的。 ②若图中存在有向环，则不可能使顶点满足拓扑次序。 ③一个DAG的拓扑序列通常表示某种方案切实可行。

就此题来说，答案应该是一般。另外给出另一方面的分析，希望能对此题有所帮助。题目：若一个有向图具有有序的拓扑排序序列，那么它的邻接矩阵必定为？（比原题加了个有序的）答案是三角。（这个三角不是特殊矩阵压缩存储时的三角矩阵，而是线性代数中的三角矩阵）可以证明，对于有向图中顶点适当地编号，使其邻接矩阵为三角矩阵且主对角元全为零的充分必要条件是该有向图可以进行拓扑排序。

拓扑排序序列有6种。先找到第一个没有被指的，就是C1，加入序列。然后擦掉跟C1有关的边，此时C2和C3都满足没有被指，选一个，比如选C2，加入序列，擦掉和C2有关的边，这个时候可以选C3,C4,C5或C6，如此而已。数据结构拓扑排序实际上是离散数学中的概念。这里不打算说太多形式化的定义，形式化的定义教科书上或者上面给的链接中就说的很详细。还是以上面选课的例子来描述这两个概念。假设我们在学习完了算法这门课后，可以选修机器学习或者计算机图形学。这个或者表示，学习机器学习和计算机图形学这两门课之间没有特定的先后顺序。因此，在我们所有可以选择的课程中，任意两门课程之间的关系要么是确定的(即拥有先后关系)，要么是不确定的(即没有先后关系)，绝对不存在互相矛盾的关系(即环路)。以上就是偏序的意义，抽象而言，有向图中两个顶点之间不存在环路，至于连通与否，是无所谓的。所以，有向无环图必然是满足偏序关系的。理解了偏序的概念，那么全序就好办了。所谓全序，就是在偏序的基础之上，有向无环图中的任意一对顶点还需要有明确的关系(反映在图中，就是单向连通的关系，注意不能双向连通，那就成环了)。可见，全序就是偏序的一种特殊情况。回到我们的选课例子中，如果机器学习需要在学习了计算机图形学之后才能学习(可能学的是图形学领域相关的机器学习算法……)，那么它们之间也就存在了确定的先后顺序，原本的偏序关系就变成了全序关系。实际上，很多地方都存在偏序和全序的概念。比如对若干互不相等的整数进行排序，最后总是能够得到唯一的排序结果(从小到大，下同)。这个结论应该不会有人表示疑问吧:)但是如果我们以偏序/全序的角度来考虑一下这个再自然不过的问题，可能就会有别的体会了。拓展到拓扑排序中，结果具有唯一性的条件也是其所有顶点之间都具有全序关系。如果没有这一层全序关系，那么拓扑排序的结果也就不是唯一的了。在后面会谈到，如果拓扑排序的结果唯一，那么该拓扑排序的结果同时也代表了一条哈密顿路径。

拓扑排序一．定义对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序(Topological Sort),是将G中所有顶点排成一个线性序列,使得对图中任意一对顶点u和v,若＜u,v＞∈E(G),则u在线性序列中出现在v之前。通常将这样的线性序列称为满足拓扑次序(Topolgical Order)的序列,简称拓扑序列。二．算法1.无前趋的顶点优先:(1)算法描述：(a)从网中选择一个入度为零的顶点输出；(b)删除该顶点及其于该点有关的所有边；(c)是否还有入度为零的顶点？若有，执行(a)，否则结束。算法实现以邻接表为图的存储结构的算法：a)扫描顶点表，将入度为零的顶点入栈；b)当栈非空时：输出栈顶元素v，出栈；检查v的出边，将每条出边的终端顶点的入度减1，若该顶点入度为0，入栈；c)当栈空时，若输出的顶点小于顶点数，则说明AOV网有回路，否则拓扑排序完成。算法实现：void Graph::Toplogicasort()//top是入度为0的顶点栈的栈顶指针 { int top=-1; for(int i=0;i<n;i++) //建立如度为0顶点的链栈 if (count[i]==0) { count[i]=top; top=i; } for(int i=0;i<n;i++) if(top==-1) { cout<<"Network has a cycle"<<endl; return; } else { int j=top;top=count[top];//入度为0的顶点出栈 count<<j<<endl; Edge<float> *l=NodeTable[j].adj; while(l) { int k=l,dest; if(--count[k]==0) { count[k]=top;//入度减至0的顶点进栈 top=k; } l=l->link;//取j的下一条出边 } } } /*通常的拓扑算法要用两个数组，一个用来记录每个顶点的入度，当入度为0，则进栈 。另一个数组用作栈数组，记录入度为0的顶点。其实当入度为0的顶点进栈以后，count[i] ＝0就不再有用，所以可以用count[i]记录栈内下一个入度为0的顶点，top指向栈顶顶点号 */

こちらの物は お気に召しましたら、持てるだけ お持ち帰りください。こちらの物--这些东西お気に召しましたら--お気に入る的尊敬语，意思是称心，如意，称意;喜爱，喜欢。~たら表示的是假设。这句话的意思是:要是您喜欢的话。持てるだけ お持ち帰りください--持てる是持つ的可能型，后面加一个だけ、表示能尽量拿，这句话是意思是:请您尽管拿，也就是说您能拿多少就拿多少。整句话的意思是:这些东西，您要是喜欢的话，就请您尽管拿吧。

就此题来说，答案应该是一般。另外给出另一方面的分析，希望能对此题有所帮助。题目：若一个有向图具有有序的拓扑排序序列，那么它的邻接矩阵必定为？（比原题加了个有序的）答案是三角。（这个三角不是特殊矩阵压缩存储时的三角矩阵，而是线性代数中的三角矩阵）可以证明，对于有向图中顶点适当地编号，使其邻接矩阵为三角矩阵且主对角元全为零的充分必要条件是该有向图可以进行拓扑排序。

针对该题，可能的拓扑排序：1.c->d->b->a->e2.d->b->c->a->e3.d->c->b->a->e当然，拓扑序列不一定唯一如果图中，这里是aov网中存在有向环，则无法完成拓扑排序。

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

2->3->1这样顺序的图即可，直接就排除对称和三角了。答案是三角。（这个三角不是特殊矩阵压缩存储时的三角矩阵，而是线性代数中的三角矩阵）可以证明，对于有向图中顶点适当地编号，使其邻接矩阵为三角矩阵且主对角元全为零的充分必要条件是该有向图可以进行拓扑排序。扩展资料：给定有向图G=(VE)，并且给定该图G中的任意两个结点u和v，如果结点u与结点v相互可达，即至少存在一条路径可以由结点u开始，到结点v终止，同时存在至少有一条路径可以由结点v开始，到结点u终止，那么就称该有向图G是强连通图。对于有向图最短路问题，计算步骤与求解无向图最短路问题相同，主要区别在于：无向图最短路问题使用单标号法。单标号法是对每一点赋予一个路权标号；而有向最短路问题使用双标号法．双标号法是对每一点赋予两个标号：路径和路权。参考资料来源：百度百科-有向图

信息工程系软件技术学生课程表（拓扑排序）拓扑图为：（图不好粘贴）运用拓扑概念排序的结果：C1 , C9 , C3 , C2 , C7 , C4, C5 , C8 , C6C1计算机应用基础 C2 C语言 C3 VB语言 C4 JSP C5数字逻辑电路 C6软件工程C7计算机网络基础 C8 Java语言 C9计算机数学基础/*-------------------------------主类-----------------------------*/public class Navy1 { public static void main(String[] args) { topology(); //调用拓扑的构造方法 } public static void topology() { //构造拓扑方法 /** 声明拓扑图中的元素 定义节点和节点之间的关系 Entry(a,b)a为b的前导 **/ Entry[] relations = { new Entry(9, 2), new Entry(3,7), new Entry(7, 5), new Entry(5, 8), new Entry(8, 6), new Entry(4, 6), new Entry(1, 3), new Entry(7, 4), new Entry(9, 5), new Entry(2, 8) }; int n = 9; int n1 = 9; /*计算拓扑图中节点数*/ int[] count = { -1, 0, 0, 0, 0, 0, 0, 0, 0, 0 }; /*开辟内存空间*/ Node[] top = { null, null, null, null, null, null, null, null, null, null }; Node p = null; for (int i = 0; i < relations.length; i++) { count[relations[i].k]++; p = new Node(); p.suc = relations[i].k; p.next = top[relations[i].j]; top[relations[i].j] = p; } int r = 0; int[] qlink = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }; for (int i = 1; i <= n; i++) { if (count[i] == 0) { qlink[r] = i; r = i; } } int f = qlink[0]; System.out.println("题目及要求:"); System.out.println("课程排课程序。写一个程序，实现对某个专业的课程进行排课的功能。"); System.out.println("已知某专业的课程和它们的前导和后续关系（以有向图的形式表示），"); System.out.println("请用拓扑排序算法求出这些课程的优先关系并输出一种排课结果"); System.out.println("--------------------------------------"); System.out.println("08信息工程系软件技术课程表（拓扑排序）"); while (true) { System.out.println(f); if (f == 0) //结束条件 { break; } else { n1--; p = top[f]; while (true) { if (p == null) { break; } else { count[p.suc]--; if (count[p.suc] == 0) { qlink[r] = p.suc; r = p.suc; } p = p.next; } } f = qlink[f]; } } System.out.println("结束的标志为：" + n1); System.out.println("--------------------------------------------"); System.out.println("注释（数字对应的课程）："); System.out.println("1 计算机应用基础 2 C语言 3 VB语言 "); System.out.println("4 JSP 5 数字逻辑电路 6 软件工程"); System.out.println("7 计算机网络基础 8 Java语言 9 计算机数学基础"); System.out.println("--------------------------------------------"); } /*构造元素类*/ private static class Entry { public Entry(int begin, int end) //定义开始元素和结束元素 { this.j = begin; this.k = end; } int j; int k; } /*声明节点的后继*/ private static class Node { public Node(int suc, Node next) { this.suc = suc; this.next = next; } public Node() { } int suc; Node next; }}