数据结构习题各种ds07

基本概念图的存储结构图的遍历生成树最短路径拓扑排序第7章图7.1图的基本概念图的定义：一个图G是由两个集合V和E组成，V是有限的非空顶点集，E是V上的顶点对所构成的边集，分别用V（G）和E（G）来表示图中的顶点集和边集。用二元组

G=（V，E）来表示图G。

有向图与无向图若图G中的每条边都是有方向的，则称G为有向图。有向边也称为弧。若图G中的每条边都是没有方向的，则称G为无向图。完全图对有n个顶点的图，若为无向图且边数为n(n-1)/2，则称其为无向完全图；若为有向图且边数为n(n-1)，则称其为有向完全图。

邻接顶点若（vi,vj）是一条无向边，则称顶点vi和vj互为邻接点，或称vi和vj相邻接，并称边（vi,vj）关联于顶点vi和vj，或称（vi,vj）与顶点vi和vj相关联。顶点的度一个顶点v的度是与它相关联的边的条数。记作TD(v)。顶点v的入度是以v为终点的有向边的条数,记作

ID(v)。顶点v的出度是以v为始点的有向边的条数,记作OD(v)。子图设有两个图G＝(V,E)和G’＝(V’,E’)。若

V’

V且E’

E,则称图G’是图G的子图。

路径

在图G＝(V,E)

中,若存在一个顶点序列

vp1,vp2,…,vpm，使得(vi,vp1)、(vp1,vp2)、

...、(vpm,vj)均属于E，则称顶点vi到vj存在一条路径。若一条路径上除了vi

和vj

可以相同外，其余顶点均不相同，则称此路径为一条简单路径。起点和终点相同的路径称为简单回路或简单环。图的连通在无向图G中，若两个顶点vi和vj之间有路径存在，则称vi

和vj

是连通的。若G中任意两个顶点都是连通的，则称G为连通图。非连通图的极大连通子图叫做连通分量。

强连通图与强连通分量

在有向图中,若对于每一对顶点vi和vj,都存在一条从vi到vj和从vj到vi的路径,则称此图是强连通图。非强连通图的极大强连通子图叫做强连通分量。权

某些图的边具有与它相关的数,称之为权。这种带权图叫做网络。12356874ABDCE1079667123151660304535804075权图

生成树一个连通图的生成树是它的极小连通子图，在n个顶点的情形下，有n-1条边。生成林若G是一个不连通的无向图，G的每个连通分量都有一棵生成树，这些生成树构成G的生成森林，简称生成林。

7.2图的存储结构在图的邻接矩阵表示中，有一个记录各个顶点信息的顶点表，还有一个表示各个顶点之间关系的邻接矩阵。设图A=(V,E)是一个有n个顶点的图，则图的邻接矩阵是一个二维数组A.Edge[n][n]，定义：无向图的邻接矩阵是对称的，有向图的邻接矩阵一般情况下是不对称的。邻接矩阵(AdjacencyMatrix)表示法在有向图中,统计第i

行1的个数可得顶点i

的出度，统计第j列1的个数可得顶点j

的入度。在无向图中,统计第i

行(列)1的个数可得顶点i

的度。网络的邻接矩阵邻接矩阵表示法中图的类型定义：#defineMAXSIZE100/*图的顶点个数*/typedefintdatatype;typedefstruct｛

datatypevexs[MAXSIZE]；/*顶点信息表*/intedges[MAXSIZE][MAXSIZE];/*邻接矩阵*/intn，e；/*顶点数和边数*/}graph；

21435无向图BADCE有向图215346203050407080有向权图邻接矩阵表示法中无向网络的建立算法voidCreate_Graph（graph*ga）｛

inti，j，k，w；

printf("请输入图的顶点数和边数：\n")；

scanf("%d"，&(ga->n)，&(ga->e))；

printf("请输入顶点信息(顶点编号)，建立顶点信息表：\n")；

for(i=0；i<ga->n；i++)scanf("%c",&(ga->vexs[i]))；/*输入顶点信息*/for(i=0；i<ga->n；i++)/*邻接矩阵初始化*/for(j=0；j<ga->n；j++)ga->edges[i][j]=0；

for(k=0；k<ga->e；k++)/*读入边的顶点编号和权值，建立邻接矩阵*/{printf("请输入第%d条边的顶点序号i，j和权值w：",k+1)；

scanf("%d，%d，%d"，&i，&j，&w)；

ga->edges[i][j]=w；

ga->edges[j][i]=w；

}}算法分析该算法的执行时间是O(n+n2+e)，由于e<n2，所以算法的时间复杂度为O(n2)。邻接表(AdjacencyList)表示法无向图的邻接表表结点表头结点datafirstvertexnextv1v2v3v4v1

v2

v3

v4

21123^4^4^3^

datafirstvertexnextG5

每个链表的上边附设一个表头结点，在表头结点中，除了设有链域first用于指向链表中第一个结点之外，还设有存储顶点vi名或其它有关信息的数据域data。把同一个顶点发出的边链接在同一个边链表中，链表的每一个结点代表一条边，叫做表结点，结点中保存有与该边相关联的另一顶点的顶点下标vertex

和指向同一链表中下一个表结点的指针next。有向图的邻接表和逆邻接表在有向图的邻接表中，第i

个边链表链接的边都是顶点i

发出的边。也叫做出边表。在有向图的逆邻接表中，第i

个边链表链接的边都是进入顶点i

的边。也叫做入边表。2^13^V1V2V32^1^2^V1V2V3G6

邻接表逆邻接表v1v2v3邻接表的类型定义#definenmax100/*假设顶点的最大数为100*/typedefstructnode*pointer；structnode{/*表结点类型*/ intvertex；

structnode*next；

}nnode；typedefstruct{/*表头结点类型，即顶点表结点类型*/ datatypedata；

pointerfirst；/*边表头指针*/ }headtype；typedefstruct{/*表头结点向量，即顶点表*/ headtypeadlist[nmax]; intn，e；

}lkgraph；建立无向图邻接表的算法

voidcreatqraph（Ikgraph*ga）｛/*建立无向图的邻接表*/inti，j，e，k；pointerp；printf(“请输入顶点数：\n”)；scanf(“%d”，&(ga->n))；for(i=1;i<=ga->n;i++){/*读入顶点信息，建立顶点表*/ scanf(“\n%c”，&(ga->adlist［i］．data))；

ga->adlist［i］．first=NULL； ｝e=0；scanf(“\n%d,%d\n”，&i，&j)；/*读入一个顶点对号i和j*/while(i>0){/*读入顶点对号,建立边表*/e++；/*累计边数*/p=(pointer)malloc(size(structnode))；/*生成新的邻接点序号为j的表结点*/p->vertex=j;p->next=ga->adlist[i]．first；ga->adlist[i].first=p；/*将新表结点插入到顶点vi的边表的头部*/p=(pointer)malloc(size(structnode))；/*生成邻接点序号为i的表结点*/p->vertex=i；p->next=ga->adlist[j].first;ga->adlist[j].first=p；/*将新表结点插入到顶点vj的边表头部*/scanf(“\n%d,%d\n”，&i，&j)；/*读入一个顶点对号i和j*/｝ga->e=e；｝该算法的时间复杂度是O（n＋e）在邻接表的边链表中，各个表结点的链入顺序任意，视表结点输入次序而定。设图中有n个顶点，e条边，则用邻接表表示无向图时，需要n个表头结点，2e个表结点；用邻接表表示有向图时，若不考虑逆邻接表，只需n个表头结点，e个表结点。带权图的边结点中还应保存该边上的权值cost。网络(带权图)的邻接表表结点vertexcostnext7.3图的遍历从已给的连通图中某一顶点出发，沿着一些边访遍图中所有的顶点，且使每个顶点仅被访问一次，就叫做图的遍历

(GraphTraversal)。图中可能存在回路，且图的任一顶点都可能与其它顶点相通，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点。为了避免重复访问，可设置一个标志顶点是否被访问过的辅助数组visited[]，它的初始状态为0，在图的遍历过程中，一旦某一个顶点i被访问，就立即让visited[i]为1，防止它被多次访问。深度优先搜索DFS(DepthFirstSearch)深度优先搜索的示例DFS在访问图中某一起始顶点v后，由v出发，访问它的任一邻接顶点v1；再从v1出发，访问与

v1邻接但还没有访问过的顶点v2；然后再从v2出发，进行类似的访问，…如此进行下去，直至到达所有的邻接顶点都被访问过的顶点vk

为止。接着，退回一步，退到前一次刚访问过的顶点，看是否还有其它没有被访问的邻接顶点。如果有，则访问此顶点，之后再从此顶点出发，进行与前述类似的访问；如果没有，就再退回一步进行搜索。重复上述过程，直到连通图中所有顶点都被访问过为止。深度优先搜索算法voidDFS（graph*g）/*按深度优先搜索法遍历图g*/

｛

inti；

for（i＝0；i＜g->n；i++）

visid[i]=0；/*初始化数组visid，使每个元素为0*/ /*标示图中的每个结点都未曾访问过*/for（i=0；i<g->n；i++）

if（!visid[i]）

DFSM(g，i)；/*调用函数DFSM，对图进行遍历*/

｝voidDFSM（graph*g，inti）/*邻接矩阵上进行DFS遍历*/

｛intj；

printf（"深度优先遍历结点：%c\n"，g->vexs[i]）；

visid[i]=1;/*假定g->vexs[i]为顶点的编号，然后变访问标志为1*/for（j=0；j<g->n；j++）

if（（g->edges[i][j]==1）＆＆！visid[j]）

DFSM（g，j）；

}voidDFSL（lkgraph*g，intn）/*邻接表上进行DFS遍历*/

｛pointerp;intj；

printf（"%d\n"，g->adlist[n].data）；

/*访问出发点，输出顶点数据*/visid[i]=1;/*然后变访问标志为1*/for（p=g->adlist[n].first；p!=NULL；p=p->next）

if（！visid[p->vertex]）

DFSL（g，p->vertex）；

}算法分析图中有n个顶点，e条边。如果用邻接表表示图，沿链可以找到某个顶点v的所有邻接顶点vi

。由于总共有2e个边结点，所以扫描边的时间为O(e)。而且对所有顶点递归访问1次，所以遍历图的时间复杂性为O(n+e)。如果用邻接矩阵表示图，则查找每一个顶点的所有邻接点，所需时间为O(n)，则遍历图中所有的顶点所需的时间为O(n2)。广度优先搜索BFS(BreadthFirstSearch

)广度优先搜索的示例

广度优先搜索过程 广度优先生成树使用广度优先搜索在访问了起始顶点v之后，由v出发，依次访问v的各个未曾被访问过的邻接顶点v1,v2,…,vt，然后再顺序访问v1,v2,…,vt的所有还未被访问过的邻接顶点。再从这些访问过的顶点出发，再访问它们的所有还未被访问过的邻接顶点，…如此做下去，直到图中所有顶点都被访问到为止。广度优先搜索是一种分层的搜索过程，每向前走一步可能访问一批顶点，不像深度优先搜索那样有往回退的情况。因此，广度优先搜索不是一个递归的过程，其算法也不是递归的。为了实现逐层访问，算法中使用了一个队列，以记忆正在访问的这一层和上一层的顶点，以便于向下一层访问。与深度优先搜索过程一样，为避免重复访问，需要一个辅助数组visited[]，以便给被访问过的顶点加标记。广度优先搜索算法voidBFS（graph*g，intv）/*v是出发顶点的序号，按广度优先搜索法遍历图g，采用邻接矩阵存储结构，BFS遍历*/｛intj，n；seqqueueq；/*假设采用顺序队列，定义顺序队列类型变量q*/n=g->n；init_seqqueue（＆q）；/*队列初始化*/printf(“访问出发点%d”,v)；/*访问出发点，假设为输出顶点序号*/visid[v]=1；/*置访问标志为1，表示此点已访问过*/en_sqqueue（＆q，v）；/*顶点v入队*/while(!empty_Seqqueue(＆q))｛/*队列空否？*/ de_sqqueue（＆q，＆v）；/*队列非空时，出队*/ for（j=l；j<=n；j++）

if（q->adges[v][j]==l＆＆！visid[j]） ｛printf(“访问顶点%d”，j)；visid[j]=1；/*置顶点j被访问标志*/ en_seqqueue(＆q，j)；/*顶点j入队*/

｝｝｝voidBFSL（graph*g，intv）｛/*采用邻接表存储结构，BFS遍历*/seqqueueq；/*假设采用顺序队列,定义顺序队列类型变量q*/pointerp；init_seqqueue（＆q）；/*队列初始化*/printf（“访问出发点%d”,v）；/*访问出发点，假设为输出顶点序号*/visid[v]=1；/*置访问标志为1，表示此点已访问过*/en_seqqueue（＆q，v）；/*顶点v入队*/while（！empty_seqqueue（＆q））｛de_seqqueue（＆q，＆v）；p=g->adlist[v]．first；While（p!=NULL）｛if（!visid[p->vertex]）｛printf("%d”，p->vertex)；visid[p->vertex]=1；en_seqqueue(＆q，p->vertex)；｝p=p->next；｝｝｝算法分析当使用邻接矩阵表示图时，因为每个顶点均入队、出队一次，所以算法BFS的外循环次数为n，且其内循环也是n次，因此算法BFS的时间复杂度为O(n2)。当使用邻接表表示图时，同样知道函数BFSL的外循环次数也是n，且其内循环次数取决于各顶点的边表结点个数，而内循环执行的总次数是边表结点的总个数2e，因此执行函数BFSL的时间复杂度是O(n+e)。非连通图的遍历非连通图的遍历必须多次调用深度优先搜索或广度优先搜索算法，以DFS为例：TRAVER()/*遍历用邻接矩阵表示的非连通图*/{inti;for(i=0;i<n;i++)visited[i]=FALSE;/*标志数组初始化*/for(i=0;i<n;i++){if(!visited[i])DFS(i);/*从顶点出发遍历一个连通分量*/printf(“compend\n”);}}7.4生成树

连通图G的一个子图如果是一棵包含G的所有顶点的树，则该子图称为G的生成树。生成树是连通图的极小连通子图。所谓极小是指：若在树中任意增加一条边，则将出现一个回路；若去掉一条边，将会使之变成非连通图。生成树各边的权值总和称为生成树的权。权最小的生成树称为最小生成树。

用不同的遍历图的方法，可以得到不同的生成树；从不同的顶点出发，也可能得到不同的生成树。按照生成树的定义，n个顶点的连通网络的生成树有n个顶点、n-1条边。

构造最小生成树，要解决以下两个问题：1.尽可能选取权值小的边，但不能构成回路。2.选取n-1条恰当的边以连接网的n个顶点。构造最小生成树的普里姆(Prim)算法普里姆算法的基本思想：从连通网络N={V,E}中的某一顶点u0出发，选择与它关联的具有最小权值的边(u0,v)，将其顶点加入到生成树的顶点集合U中。以后每一步从一个顶点在U中，而另一个顶点不在U中的各条边中选择权值最小的边(u,v),把它的顶点加入到集合U中。如此继续下去，直到网络中的所有顶点都加入到生成树顶点集合U中为止。用普里姆算法构造最小生成树的过程123465565173254612346551324Prim算法的形式描述如下：置T为任意一个顶点；求初始候选边集；

while（T中结点数＜n）｛从候选边集中选取最短边（u，v）；将（u，v）及顶点v，扩充到T中；调整候选边集；｝PRIM算法voidprim（graph*g，intu）

{intv，k，j，min；for(v=1；v<=g->n；v++)if（v!=u）｛minedge[v].end=u；minedge[v].len=g->edges[v][u]；｝minedge[u].len=0；for（k=1；k<g->n；k++）｛min=minedge[k].len；v=k；for（j=1；j<g->n；j++）if（minedge[j].len>0&&minedge[j].len<min）｛min=minedge[j].len；v=j；｝if（min=INTMAX）{

printf(“图不连通，无生成树！”)；return(0)；}

printf(“%d%d”,v,minedge[v].end)；minedge[v].len=-minedge[v].len；for(j＝1；j<=g->n；j++)if（g->edges[j][v]<minedge[j].len）｛minedge[j].len=g->edges[j][v]；minedge[j].end=v；｝｝｝算法分析

上述算法的初始化时间是O(1)，k循环中有两个循环语句，其时间大致为：

令O(1)为某一正常数C，展开上述求和公式可知其数量级仍是n的平方。所以，整个算法的时间复杂性是O(n2)。构造最小生成树的克鲁斯卡尔(Kruskal)算法克鲁斯卡尔算法的基本思想：设有一个有n个顶点的连通网络N={V,E},最初先构造一个只有n个顶点，没有边的非连通图T={V,

},图中每个顶点自成一个连通分量。当在E中选到一条具有最小权值的边时,若该边的两个顶点落在不同的连通分量上，则将此边加入到T中；否则将此边舍去，重新选择一条权值最小的边。如此重复下去，直到所有顶点在同一个连通分量上为止。用克鲁斯卡尔算法构造最小生成树的过程123465565173254612346551324克鲁斯卡尔算法的形式描述如下：T=(V,φ)；While(T中所含边数<n-1){从E中选取当前最短边(u,v);

从E中删除边(u,v);if((u,v)并入T之后不产生回路)

将边(u,v)并入T中；

}typedefStruct｛

intv1，v2；

intlen；

}edgetype；/*边的类型：两个端点号和边长*/intparent[nmax+1]；/*结点双亲的指针数组，设为全局量，nmax为结点数最大值*/intgetroot（intv）/*找结点v所在的树根*/｛inti；

i=v；while（parent[i]>0）i=parent[i]；returni；/*若无双亲（初始点），双亲运算结果为其自己*/

｝intgetedge（edgetypeem[]，inte）/*找最短边，e为边数*/｛inti,j,min=0;for(i=1;i<=e;i++)if(em[i-1].len<min)min=em[i-1].len；returnmin；｝Kruskal算法voidkruskal（edqetypeem[]，intn，inte）/*n为结点数，e为边数*/｛inti，p1，p2，m，i0；for（i=1；i<=n；i++）/*初始结点为根，无双亲*/parent[i]=-1；/*以后用于累计结点个数，此初值不能置为0*/m=1；while（m<n）｛i0=getedge（em，e）；/*获得最短边号*/p1=getroot（em[i0].v1）；p2=getroot（em[i0].v2）;if（p1==p2）continue；/*连通分量相同，不合并*/if（p1>p2）｛parent［p2］=parent［p1］＋parent［p2］；/*p2的双亲中累计结点总数（为负值）*/parent[pl]=p2；/*p1成为p2的孩子｝else｛parent[p1]=parent[p1]＋parent[p2];parent[p2]=p1;｝m++；printf(“%d%d%d\n”，m，em[i0].v1，em[i0].v2)；｝｝算法分析

用Kruskal算法构造最小生成树的时间复杂度为O（eloge），与网中边的数目e有关，因此，它适用于求稀疏图的最小生成树。7.5最短路径最短路径问题：如果从图中某一顶点(称为源点)到达另一顶点(称为终点)的路径可能不止一条，如何找到一条路径，使得沿此路径各边上的权值总和达到最小。问题解法：单源最短路径—

Dijkstra算法任意顶点对之间的最短路径—Floyd算法单源最短路径问题问题的提出：给定一个带权有向图G与源点v，求从v到G中其它顶点的最短路径。限定各边上的权值大于或等于0。为求得这些最短路径，Dijkstra提出按路径长度的递增次序，逐步产生最短路径的算法。首先求出长度最短的一条最短路径，再参照它求出长度次短的一条最短路径，依次类推，直到从顶点v到其它各顶点的最短路径全部求出为止。举例说明Dijkstra逐步求解的过程１２５３４10301020Dijkstra算法voiddijkstra（graph*G，intv，int*dist,int*path,char*S）{inti,j,k,pre，min；for（i=l;i<=G->n;i++）

{s[i]=0；dist[i]=G->adges[v][i]；path[i]=V；｝s[v]=1；dist[v]=0；for（i＝1；i<G->n；i++）｛min=INTMAX；for(j=1;j<=G->n；j++)if(！s[j]&&dist[j]<min){min＝dist[j];k=j;}if(min==INTMAX)break;S[k]=1；for（j＝l；j<=G->n；j++）if（！s[j]&&dist[j]>dist[k]+G->adges[k][j]）｛dist[j]=dist[k]+G->adges[k][j]；Path[j]=k;｝｝

for（i=1；i<=G->n；i++）{printf(“顶点%d的最短路径为：%d\n”，i，dist［i］)；Pre＝path[i]；do｛printf(“<-%d”,pre)；pre=path[pre]；｝while（pre！=v）；if(dist[i]==INTMAX)printf(”无路径\n”)；｝}算法说明对于顶点i和j：1、首先，考虑从i到j是否有以顶点1为中间点的路径，：i，1，j，即考虑图中是否有边<i,1>和<1,j>，若有，则新路径i，1，j的长度是C[i][1]+C[1][j]，比较路径i，j和i，1，j，的长度，并以较短者为当前所求得的最短路径，。该路径是中间点序号不大于1的最短路径。所有顶点对之间的最短路径2、其次，考虑从i到j是否包含顶点2为中间点的路径：i，...，2，...，j，若没有，则从i到j的最短路径仍然是第一步中求出的，即从i到j的中间点序号不大于1的最短路径；若有，则i，...，2，...，j可分解成两条路径i，...，2和2，...，j，而这两条路径是前一次找到的中间点序号不大于1的最短路径，将这两条路径相加就得到路径i，...，2，...，j的长度，将该长度与前一次求出的从i到j的中间点序号不大于1的最短路径长度比较，取其较短者作为当前求得的从i到j的中间点序号不大于2的最短路径。3、然后，再选择顶点3加入当前求得的从i到j中间点序号不大于2的最短路径中，按上述步骤进行比较，从未加入顶点3作中间点的最短路径和加入顶点3作中间点的新路径中选取较小者，作为当前求得的从i到j的中间点序号不大于3的最短路径。依次类推，直到考虑了顶点n加入当前从i到j的最短路径后，选出从i到j的中间点序号不大于n的最短路径为止。由于图中顶点序号不大于n，所以从i到j的中间点序号不大于n的最短路径，已考虑了所有顶点作为中间点的可能性。因而它必是从i到j的最短路径。算法的基本思想就是：从初始的邻接矩阵A0开始，递推地生成矩阵序列A1，A2，...，An显然，A中记录了所有顶点对之间的最短路径长度。若要求得到最短路径本身，还必须设置一个路径矩阵P[n][n]，在第k次迭代中求得的path[i][j]，是从i到j的中间点序号不大于k的最短路径上顶点i的后继顶点。算法结束时，由path[i][j]的值就可以得到从i到j的最短路径上的各个顶点。Floyd算法voidfloyd（graph*G）｛

inti，j，k，next；

for(i=1；i<=G->n；i++)for（j＝1；j<=G->n；j++）｛

A[i][j]=G->adges[i][j]；

path[i][j]=0；｝

for（k=1;k<=G->n;k++）

for(i=1；i<=G->n；i++)for（j=l；j<＝G->n；j++）

if（A[i][k]＋A[k][j]<A[i][j]）｛A[i][j]＝A[i][k]＋A[k][j]；

path[i][j]=k；｝for（i＝1；i<=G->n；i++）

for（j=1；j<=G->n；j++）｛printf（”顶点%d路径长度%d”，i，A[i][j]）；

next＝path[i][j]；

printf(“路径为：%d”，i)；do｛

printf（”－＞%d”，next）；

next=path[next][j]；｝while（next！=j）；if(A[i][j]==INTMAX)printf（“无路径\n”）；｝｝１２５３４5010301020601007.6拓扑排序计划、施工过程、生产流程、程序流程等都是“工程”。除了很小的工程外，一般都把工程分为若干个叫做“活动”的子工程。完成了这些活动，这个工程就可以完成了。例如，计算机专业学生的学习就是一个工程，每一门课程的学习就是整个工程的一些活动。其中一些课程要求有先修课程，另一些则不要求。这样在有的课程之间有先后关系，有的课程可以并行地学习。

C1

高等数学

C2

程序设计基础

C3

离散数学C1,C2

C4

数据结构C3,C2C5

高级语言程序设计C2C6

编译方法C5,C4C7

操作系统C4,C9C8

普通物理C1C9

计算机原理C8

课程代号课程名称先修课程学生课程学习工程图

可以用有向图表示一个工程。在这种有向图中，用顶点表示活动，用有向边<Vi,Vj>

表示活动的前后次序。Vi必须先于活动Vj

进行。这种有向图叫做顶点表示活动的

AOV网络(ActivityOnVertices)。在AOV网络中，如果活动Vi必须在活动Vj

之前进行，则存在有向边<Vi,Vj>，AOV

网络中不能出现有向回路，即有向环。在

AOV网络中如果出现了有向环，则意味着某项活动应以自己作为先决条件。因此，对给定的AOV网络，必须先判断它是否存在有向环。

检测有向环的一种方法是对AOV网络构造它的拓扑有序序列。即将各个顶点(代