数据结构习题解析第8章【精选文档】

《数据结构习题解析第8章【精选文档】》由会员分享，可在线阅读，更多相关《数据结构习题解析第8章【精选文档】（23页珍藏版）》请在装配图网上搜索。

1、数据结构习题解析第8章【精选文档】第8章 图一、复习要点图是一种重要的非线性结构.它的特点是每一个顶点都可以与其它顶点相关联，与树不同，图中各个顶点的地位都是平等的，对顶点的编号都是人为的。通常，定义图由两个集合构成：一个是顶点的非空有穷集合，一个是顶点与顶点之间关系(边)的有穷集合.对图的处理要区分有向图与无向图.它的存储表示可以使用邻接矩阵，可以使用邻接表，前者属顺序表示，后者属链接表示。在本章着重讨论了图的深度优先搜索和广度优先搜索算法，附带引入了生成树与生成森林的概念。对于带权图，给出了最小生成树的两种方法：Prim算法和Kruskal算法，后者使用了最小堆和并查集作为它的辅助求解手段

2、。在解决最短路径问题时，采用了逐步求解的策略。最后讨论了作工程计划时常用的活动网络。涉及的主要概念是拓扑排序和关键路径，在解决应用问题时它们十分有用.本章复习的要点是：1、基本知识点主要要求理解图的基本概念，包括图的定义、图的连通性、图的路径和路径长度、图中各顶点的度及度的度量、无向连通图的最大边数和最小边数，有向强连通图的最大边数与最小边数等。掌握图的存储表示，包括邻接矩阵和邻接表，以及这些存储表示上的典型操作，如构造、求根、找第一个邻接顶点、找下一个邻接顶点等操作的实现算法.并要求掌握图的两种遍历算法:深度优先搜索和广度优先搜索算法，以及求解连通性问题的方法。理解求解关节点及构造重连通图的

3、方法。此外，要求掌握构造最小生成树的Prim算法和Kruskal方法，掌握活动网络的拓扑排序算法，掌握求解关键路径的方法。需要注意的是，让某个关键活动提前完成，是否能让整个工程提前完成.2、算法设计 建立无向带权图的邻接表的算法，要求输入边的数目随机而定。 图的深度优先搜索的递归算法。 利用图的深度优先搜索的递归算法建立图的深度优先生成森林（用左子女右兄弟表示)的算法. 图的广度优先搜索算法。 利用图的广度优先搜索算法建立图的广度优先生成森林(用左子女右兄弟表示)的算法. 求解最小生成树的Prim算法,注意nearvex和lowcost辅助数组的变化。 求解最小生成树的Kruskal算法，注意

4、minheap和UFset的变化。 求解最短路径的dijkstra算法，注意dist辅助数组的变化。 有向图中求解拓扑排序的算法，要求用邻接表作为图的存储表示.注意算法执行过程中入度为零的顶点栈的变化。 有向图中求解拓扑排序的算法,要求用邻接矩阵作为图的存储表示。二、难点和重点1、图：图的定义与图的存储表示邻接矩阵表示(通常是稀疏矩阵) 邻接表与逆邻接表表示,要求建立算法 邻接多重表（十字链表)表示2、深度优先遍历与广度优先遍历 生成树与生成树林的定义 深度优先搜索算法和广度优先搜索算法 深度优先搜索是个递归的过程，而广度优先搜索是个非递归的过程 为防止重复访问已经访问过的顶点，需要设置一个访

5、问标志数组visited3、图的连通性深度优先搜索可以遍历一个连通分量上的所有顶点 对非连通图进行遍历，可以建立一个生成森林 对非强连通图进行遍历,可能建立一个生成森林 关节点的求解方法和以最少的边构成重连通图的方法4、最小生成树对于连通网络、可用不会构成环路的权值最小的n1条边构成最小生成树 会画出用Kruskal算法及Prim算法构造最小生成树的过程5、单源最短路径采用逐步求解的方式求某一顶点到其他顶点的最短路径的方法要求每条边的权值必须大于零6、活动网络拓扑排序、关键路径、关键活动、AOE网拓扑排序将一个偏序图转化为一个全序图。 为实现拓扑排序，要建立一个栈，将所有入度为零的顶点进栈关键

6、路径的计算三、教材中习题的解析81 画出1个顶点、2个顶点、3个顶点、4个顶点和5个顶点的无向完全图。试证明在n个顶点的无向完全图中，边的条数为n（n-1)/2。【解答】1个顶点的无向完全图2个顶点的无向完全图3个顶点的无向完全图4个顶点的无向完全图5个顶点的无向完全图【证明】在有n个顶点的无向完全图中，每一个顶点都有一条边与其它某一顶点相连，所以每一个顶点有n1条边与其他n1个顶点相连，总计n个顶点有n（n-1)条边。但在无向图中，顶点i到顶点j与顶点j到顶点i是同一条边，所以总共有n(n1)/2条边。ABCDEF82 右边的有向图是强连通的吗？请列出所有的简单路径。【解答】判断一个有向图是

7、否强连通，要看从任一顶点出发是否能够回到该顶点.右面的有向图做不到这一点，它不是强连通的有向图。各个顶点自成强连通分量。所谓简单路径是指该路径上没有重复的顶点。从顶点A出发，到其他的各个顶点的简单路径有AB，ADB，ABC,ADBC，AD，ABE，ADE，ADBE,ABCFE，ADBCFE，ABCF，ADBCF。从顶点B出发,到其他各个顶点的简单路径有BC，BCF,BE，BCFE。从顶点C出发，到其他各个顶点的简单路径有CF，CFE.从顶点D出发,到其他各个顶点的简单路径有DB，DBC，DBCF,DE，DBE，DBCFE。从顶点E出发，到其他各个顶点的简单路径无.从顶点F出发，到其他各个顶点的

8、简单路径有FE。ABCDEF83 给出右图的邻接矩阵、邻接表和邻接多重表表示.【解答】(1) 邻接矩阵32451441ABCDEF(2) 邻接表（出边表）ABCDEF03101352（入边表）data fin fout(3) 邻接多重表（十字链表)i j ilink jlinkABCDEF0 3 (A, D)3 1 (D, B)0 1 (A, B)1 2 (B, C)1 4 (B, E)5 4 (F, E)3 4 (D, E)2 5 (C, F)84 用邻接矩阵表示图时,若图中有1000个顶点,1000条边,则形成的邻接矩阵有多少矩阵元素?有多少非零元素?是否稀疏矩阵?【解答】一个图中有100

9、0个顶点，其邻接矩阵中的矩阵元素有10002 = 1000000个。它有1000个非零元素（对于有向图)或2000个非零元素（对于无向图），因此是稀疏矩阵。85 用邻接矩阵表示图时，矩阵元素的个数与顶点个数是否相关？与边的条数是否相关？【解答】用邻接矩阵表示图，矩阵元素的个数是顶点个数的平方，与边的条数无关。矩阵中非零元素的个数与边的条数有关.86 有n个顶点的无向连通图至少有多少条边？有n个顶点的有向强连通图至少有多少条边？试举例说明。【解答】n个顶点的无向连通图至少有n1条边,n个顶点的有向强连通图至少有n条边.例如：特例情况是当n = 1时，此时至少有0条边。87对于有n个顶点的无向图,

10、采用邻接矩阵表示，如何判断以下问题： 图中有多少条边?任意两个顶点i和j之间是否有边相连？任意一个顶点的度是多少？【解答】用邻接矩阵表示无向图时，因为是对称矩阵，对矩阵的上三角部分或下三角部分检测一遍,统计其中的非零元素个数，就是图中的边数.如果邻接矩阵中Aij 不为零，说明顶点i与顶点j之间有边相连。此外统计矩阵第i行或第i列的非零元素个数，就可得到顶点i的度数.8-8对于如右图所示的有向图，试写出：(1） 从顶点出发进行深度优先搜索所得到的深度优先生成树；（2） 从顶点出发进行广度优先搜索所得到的广度优先生成树； 【解答】（1) 以顶点为根的深度优先生成树（不唯一）： 或 (2) 以顶点为

11、根的广度优先生成树：89 试扩充深度优先搜索算法,在遍历图的过程中建立生成森林的左子女右兄弟链表。算法的首部为void Graph：DFS ( const int v, int visited , TreeNodeint t ） 其中,指针t指向生成森林上具有图顶点v信息的根结点.(提示:在继续按深度方向从根v的某一未访问过的邻接顶点w向下遍历之前，建立子女结点。但需要判断是作为根的第一个子女还是作为其子女的右兄弟链入生成树.）【解答】为建立生成森林，需要先给出建立生成树的算法，然后再在遍历图的过程中，通过一次次地调用这个算法，以建立生成森林。te mplateType void GraphT

12、ype : DFS_Tree （ const int v， int visited ， TreeNodeType *t ） /从图的顶点v出发, 深度优先遍历图, 建立以t (已在上层算法中建立)为根的生成树。 Visitedv = 1; int first = 1; TreeNode p, q； int w = GetFirstNeighbor （ v ）； /取第一个邻接顶点 while ( w != 1 ) /若邻接顶点存在 if ( vositedw = 0 ） /且该邻接结点未访问过 p = new TreeNode ( GetValue (w) );/建立新的生成树结点 if （

13、first = 1 )/若根t还未链入任一子女 t-setFirstChild ( p )； first = 0; /新结点p成为根*t的第一个子女 else q-setNextSibling ( p ）;/否则新结点*p成为*q的下一个兄弟 q = p；/指针q总指示兄弟链最后一个结点 DFS_Tree （ w， visited， q ）;/从q向下建立子树 w = GetNextNeighbor ( v， w );/取顶点v排在邻接顶点w的下一个邻接顶点 下一个算法用于建立以左子女右兄弟链表为存储表示的生成森林。templateType void Graph : DFS_Forest （

14、TreeType T ） /从图的顶点v出发, 深度优先遍历图, 建立以左子女-右兄弟链表表示的生成森林T。 T。root = NULL； int n = NumberOfVertices ( ）;/顶点个数 TreeNodeType * p， q; int * visited = new int n ；/建立访问标记数组 for ( int v = 0； v n; v+ ) visitedv = 0; for ( v = 0； v n； v+ ) /逐个顶点检测 if （ visitedv = 0 ) /若尚未访问过 p = new TreeNode ( GetValue ( v ) );/

15、建立新结点p if ( T.root = NULL ) T。root = p;/原来是空的生成森林， 新结点成为根 else q setNextSibling （ p ）；/否则新结点p成为q的下一个兄弟 q = p； DFS_Tree ( v， visited， p );/建立以p为根的生成树 810 用邻接表表示图时,顶点个数设为n，边的条数设为e,在邻接表上执行有关图的遍历操作时，时间代价是O(n*e)？还是O(n+e）？或者是O（max(n,e）？【解答】在邻接表上执行图的遍历操作时，需要对邻接表中所有的边链表中的结点访问一次,还需要对所有的顶点访问一次，所以时间代价是O(n+e）。8

16、11 右图是一个连通图，请画出 (1) 以顶点为根的深度优先生成树；(2) 如果有关节点，请找出所有的关节点。（3) 如果想把该连通图变成重连通图，至少在图中加几条边？如何加？【解答】(1） 以顶点为根的深度优先生成树：(2） 关节点为 ，,，（3） 至少加四条边 （1， 10）， （3， 4), (4， 5）， （5， 6）。从的子孙结点到的祖先结点引一条边，从的子孙结点到根的另一分支引一条边,并将的子孙结点、与结点连结起来，可使其变为重连通图。812试证明在一个有n个顶点的完全图中，生成树的数目至少有2n-11。【证明】略51176810978-13 编写一个完整的程序，首先定义堆和并查集

17、的结构类型和相关操作，再定义Kruskal求连通网络的最小生成树算法的实现。并以右图为例，写出求解过程中堆、并查集和最小生成树的变化。【解答】求解过程的第一步是对所有的边，按其权值大小建堆：1 2 71 3 112 3 101 3 113 4 51 2 72 3 102 4 91 3 111 2 72 4 92 3 10加(1, 2), (1, 3), (2,3)加(2, 4)加(3, 4)1 3 113 4 51 2 73 5 72 4 92 3 103 6 81 3 113 4 51 2 73 5 72 4 92 3 10加(3, 5)加(3, 6)1 2 73 4 55 6 63 5 7

18、2 4 92 3 103 6 81 3 11加(5, 6)求解过程中并查集与堆的变化：1 3 115 6 61 2 73 5 72 4 92 3 103 6 81 2 73 5 73 6 8选(5,6,6)1 3 112 4 92 3 10选(3,4,5)1 3 113 5 72 4 92 3 103 6 81 3 112 4 92 3 103 6 8选(1,2,7)选(3,5,7)1 3 112 3 101 3 112 3 102 4 9选(3,6,8), 在同一连通分量上, 不加选(2,4,9), 结束3 1 -6 3 3 5 0 1 2 3 4 5 6最后得到的生成树如下67579并查集

19、的存储表示完整的程序如下:#include iostream.htemplate class Type class MinHeap public: enum MaxHeapSize = 50 ; MinHeap （ int Maxsize = MaxHeapSize ); MinHeap ( Type Array ， int n ）; void Insert ( const Type &ele ）; void RemoveMin ( Type &Min ); void Output (); private: void FilterDown （ int start, int end ）; voi

20、d FilterUp （ int end )； Type*pHeap； int HMaxSize; int CurrentSize;class UFSets public： enum MaxUnionSize = 50 ; UFSets ( int MaxSize = MaxUnionSize ）; UFSets （） delete m_pParent; void Union ( int Root1， int Root2 ）; int Find （ int x ）;private： int m_iSize； int m_pParent；;class Graph public： enum Max

21、VerticesNum = 50 ; Graph（ int Vertices = 0) CurrentVertices = Vertices； InitGraph（）; void InitGraph （）; void Kruskal （); int GetVerticesNum （） return CurrentVertices； private: int EdgeMaxVerticesNumMaxVerticesNum; int CurrentVertices；;class GraphEdge public: int head， tail; int cost; int operator =

22、( GraphEdge ed ）；;GraphEdge : operator = ( GraphEdge ed ） return thiscost = 0 ) x = m_pParentx； return x；template MinHeapType :： MinHeap （ int Maxsize ） HMaxSize = Maxsize； pHeap = new TypeHMaxSize; CurrentSize = 1;template class Type MinHeapType : MinHeap ( Type Array, int n ） HMaxSize = （ n MaxHea

23、pSize ） ? MaxHeapSize ： n; pHeap = new TypeHMaxSize; for ( int i = 0; i n； i+ ) pHeapi = Arrayi； CurrentSize = n-1； int iPos = ( CurrentSize 1 ) / 2； while ( iPos = 0 ) FilterDown （ iPos, CurrentSize ）； iPos-; template class Type void MinHeapType ： FilterDown （ int start, int end ) int i = start， j

24、= 2 start + 1; Type Temp = pHeapi; while ( j = end ) if ( j end & pHeapj+1 = pHeapj ) j+; if ( Temp = pHeapj ） break； pHeapi = pHeapj； i = j； j = 2 * j + 1； pHeapi = Temp;template void MinHeap ：: FilterUp ( int end ) int i = end， j = ( end 1 ） / 2; Type Temp = pHeapi; while （ i 0 ） if ( pHeapj = Tem

25、p ） break; pHeapi = pHeapj; i = j； j = ( j - 1 ） / 2； pHeapi = Temp；template void MinHeapType : Insert （ const Type &ele ) CurrentSize+； if （ CurrentSize = HMaxSize ) return； pHeapCurrentSize = ele; FilterUp （ CurrentSize )；template void MinHeapType ：: RemoveMin ( Type Min ） if ( CurrentSize 0 ） ret

26、urn； Min = pHeap0； pHeap0 = pHeapCurrentSize; FilterDown （ 0, CurrentSize )；template class Type void MinHeapType :： Output （ ) for （ int i = 0； i = CurrentSize； i+ ) cout pHeapi ” ； cout endl；void Graph ： InitGraph（ ) Edge00 = 1； Edge01 = 28; Edge02 = 1； Edge03 = 1； Edge04 = -1； Edge05 = 10； Edge06

27、= -1; Edge11 = 1; Edge12 = 16； Edge13 = 1; Edge14 = -1; Edge15 = -1; Edge16 = 14； Edge22 = 1; Edge23 = 12; Edge24 = -1; Edge25 = 1； Edge26 = -1； Edge33 = 1； Edge34 = 22; Edge35 = 1； Edge36 = 18； Edge44 = 1； Edge45 = 25； Edge46 = 24; Edge55 = 1； Edge56 = 1； Edge66 = 1; for ( int i = 1； i 6; i+ ） for

28、( int j = 0； j i; j + ） Edgeij = Edgeji；void Graph :： Kruskal( ) GraphEdge e； int VerticesNum = GetVerticesNum ( ); int i， j， count； MinHeapGraphEdge heap ( VerticesNum *VerticesNum ); UFSets set ( VerticesNum )； for （ i = 0; i VerticesNum； i+ ） for ( j = i + 1; j VerticesNum; j+ ） if ( Edgeij 0 ） e

29、。head = i; e。tail = j; e.cost = Edgeij;heap.Insert （ e ); count = 1； while （ count VerticesNum ） heap.RemoveMin ( e ）； i = set.Find （ e。head ); j = set.Find ( e.tail ）； if ( i ！= j ) set。Union ( i， j ）;count+;cout ”（ ” e。head ”, ” e。tail ”， e.cost ” ）” endl； 8-14 利用Dijkstra算法的思想，设计一个求最小生成树的算法。【解答】计算

30、连通网络的最小生成树的Dijkstra算法可描述如下：将连通网络中所有的边以方便的次序逐步加入到初始为空的生成树的边集合T中。每次选择并加入一条边时，需要判断它是否会与先前加入T的边构成回路.如果构成了回路，则从这个回路中将权值最大的边退选. 下面以邻接矩阵作为连通网络的存储表示,并以并查集作为判断是否出现回路的工具，分析算法的执行过程。262111181416199561416211614211995并查集, 表明4个结点在同一连通分量上914165614165619111914165611最终得到的最小生成树为算法的思路如下：1 并查集初始化：将所有顶点置为只有一个顶点的连通分量；2 检查

31、所有的边：)若边的两个端点i与j不在同一连通分量上(i与j在并查集中不同根),则连通之（合并)；） 若边的两个端点i与j在同一连通分量上(i与j在并查集中同根），则 在并查集中寻找离i与j最近的共同祖先结点 分别从i与j向上检测具有最大权值的边 在并查集上删除具有最大权值的边，加入新的边。下面给出实现算法：const int MaxNum = 10000；void Graph :： Dijkstra ( ) GraphEdge e； int VerticesNum = GetVerticesNum （ ）； int i， j, p, q, k; int disJointVerticesNum；

32、/并查集 for （ i = 0； i VerticesNum； i+ ） disJointi = -1； /并查集初始化 for （ i = 0; i VerticesNum-1； i+ )/检查所有的边 for （ j = i + 1； j VerticesNum； j+ ） if （ Edgeij = 0 ) p = disJointp； while ( disJointq = 0 ） p = disJointq; if （ p != q ) disJointj = i；/ i与j不在同一连通分量上, 连通之 else / i与j在同一连通分量上 p = i;/寻找离结点i与j最近的祖先

33、结点 while （ disJointp = 0 ) /每变动一个p, 就对q到根的路径检测一遍 q = j； while （ disJointq = 0 & disJointq = disJointp )q = disJointq； if ( disJointq = disJointp ) break； else p = disJointp; k = disJointp;/结点k是i和j的最近的共同祖先 p = i； q = disJointp； max = -MaxNum;/从i到k找权值最大的边（s1, s2) while ( q = k ） if （ Edgeqp max ) max

34、= Edgeqp； s1 = p; s2 = q； p =q; q = disJointp； p = j； q = disJointp; max = -MaxNum;/从j到k找权值最大的边(t1， t2) while ( q = k ) if （ Edgeqp max ） max = Edgeqp； t1 = p; t2 = q; p =q； q = disJointp; max = Edgeij; k1 = i; k2 = j; if （ max Edges1s2 ) max = Edges1s2; k1 = s1； k2 = s2； if ( max Edget1t2 ) max = E

35、dget1t2； k1 = t1； k2 = t2; if ( max != Edgeij ) /当Edgeij = max时边不改 if （ disJointk1 = k2 ) disJointk1 = 1； else disJointk2 = -1；/删除权值最大的边 disJointj = i；/加入新的边 Edgeji = Edgeji; 101855222ABCDE815以右图为例，按Dijkstra算法计算得到的从顶点（A）到其它各个顶点的最短路径和最短路径长度。【解答】源点终点最短路径最短路径长度 A B(A,B)(A，B）（A，B）(A,B）10101010 C(A,C）（A，

36、C）(A，C）（A,C)18181818 D （A，B,D）(A,B,D)(A，B，D）151515 E （A,B，D，E）(A,B，D,E）1717816 在以下假设下，重写Dijkstra算法：（1) 用邻接表表示带权有向图G，其中每个边结点有3个域：邻接顶点vertex,边上的权值length和边链表的链接指针link。(2） 用集合T = V(G) S代替S (已找到最短路径的顶点集合)，利用链表来表示集合T。试比较新算法与原来的算法,计算时间是快了还是慢了,给出定量的比较.【解答】(1) 用邻接表表示的带权有向图的类定义：const int DefaultSize = 10；/缺省顶

37、点个数class Graph;/图的前视类定义struct Edge /边的定义friend class Graph； int vertex；/边的另一顶点位置 float length；/边上的权值 Edge link;/下一条边链指针 Edge ( ） /构造函数 Edge （ int num, float wh ) : vertex （num)， length (wh）， link (NULL) /构造函数 int operator = 0 i NumVertices ？ NodeTablei。data : ； float GetWeight ( int v1, int v2 ）;/返回

38、边(v1， v2）上的权值 int GetFirstNeighbor （ int v ）；/取顶点v的第一个邻接顶点 int GetNextNeighbor ( int v， int w ）；/取顶点v的邻接顶点w的下一个邻接顶点（2) 用集合T = V(G） - S代替S （已找到最短路径的顶点集合）,利用链表来表示集合T. 集合T用有序链表表示，数据域为顶点序号，链表T中的顶点都是未找到最短路径的顶点.另外设置一个数组S,其作用是记录已找到的顶点0到其他各顶点的最短路径path及最短路径长度len.算法的主要思路是:1 对数组S及链表T初始化，记录顶点0到各个顶点的初始最短路径及其长度；2

39、 扫描链表T,寻找链表T中各个顶点到顶点0的当前最短路径中长度最小者，记为u;3 在邻接表中扫描第u个顶点的出边表，确定每一边的邻接顶点号k。若顶点k的最短路径没有选中过，比较绕过顶点u到顶点k的路径长度和原来顶点0到顶点k的最短路径长度,取其小者作为从顶点0到顶点k的新的最短路径。4 重复执行、步，直到图中所有顶点的最短路径长度都已选定为止。算法的实现如下：const float MaxNum = 10000000;typedef struct info /辅助数组元素: 各顶点最短路径信息 int pre;/在最短路径上前一顶点的顶点序号 float len；/当前最短路径长度info S

40、 NumVertices;/辅助数组: 最短路径数组Listint T;/未选定最短路径顶点链表int i， k， u； ListNode * p；T. MakeEmpty （）;for （ i = 1; i vertex.len = p-length； p = plink； while （1) T.First ()；/循环检测链表T if ( ！ T.NextNotNull（ ) ) break;/链表仅剩一个顶点， 跳出循环， 算法结束 float min = MaxNum; u = 0； while ( T。NotNull( ） ) /链表不空， 还有剩余顶点未确定最短路径 i = T。

41、GetData( ）; /取剩余顶点号 if （ Si.len vertex;/顶点k在链表T中表示该顶点未最终选定最短路径 if ( T。Find(k) != NULL Su.len + plength Sk.len ) sk.len = Su.len + plength; Sk.pre = u； /修改 p = plink; T。Find（u); T。Remove（）;/在链表T中删除顶点u 8-17 试证明：对于一个无向图G = （V， E)，若G中各顶点的度均大于或等于2，则G中必有回路。【解答】反证法：对于一个无向图G=（V，E），若G中各顶点的度均大于或等于2,则G中没有回路。此时

42、从某一个顶点出发,应能按拓扑有序的顺序遍历图中所有顶点。但当遍历到该顶点的另一邻接顶点时,又可能回到该顶点，没有回路的假设不成立。8-18 设有一个有向图存储在邻接表中。试设计一个算法，按深度优先搜索策略对其进行拓扑排序。并以右图为例检验你的算法的正确性。【解答】(1) 利用题816定义的邻接表结构。增加两个辅助数组和一个工作变量:w 记录各顶点入度 int indegreeNumVertices。w 记录各顶点访问顺序 int visitedNumVertices,初始时让visitedi = 0, i = 1, 2， ， NumVertices。w 访问计数int count，初始时为0。

43、（2) 拓扑排序算法void Graph ：: dfs ( int visited , int indegree , int v， int count ） count+; visitedv = count; cout vertex; indegreew-; if （ visitedw = 0 & indegreew = 0 ） dfs （ visited， indegree， w， count ）; p = plink; 主程序int i， j； Edge p; float w;cin NumVertices；int * visited = new intNumVertices+1;int *

44、 indegree = new intNumVertices+1；for （ i = 1； i = NumVertices； i+ ） NodeTablei.adj = NULL; cin NodeTablei.data； cout i j w; cout endl;while ( i ！= 0 & j != 0 ) p = new Edge ( j， w ); if （ p = NULL ) cout “存储分配失败！” link = NodeTablei.adj; NodeTablei.adj = p； NumEdges+； cin i j w； cout endl；for （ i = 1

45、； i = NumVertices; i+ ） if （ visitedi = 0 & indegreei = 0 ) dfs ( visited， indegree， i， count ）；if ( count NumVertices ) cout “排序失败!” endl； else cout “排序成功!” endl；delete visited； delete indegree;8-19 试对下图所示的AOE网络，解答下列问题。（1) 这个工程最早可能在什么时间结束.（2） 求每个事件的最早开始时间Vei和最迟开始时间Vli。（3) 求每个活动的最早开始时间e（ ）和最迟开始时间l( )。(4） 确定哪些活动是关键活动。画出由所有关键活动构成的图,指出哪些活动加速可使整个工程提前完成。【解答】按拓扑有序的顺序计算各个顶点的最早可能开始时间Ve和最迟允许开始时间Vl。然后再计算各个活动的最早可能开始时间e和最迟允许开始时间l，根据l e = 0？ 来确定关键活动，从而确定关键路径. 1 2 3 4 5 6 Ve 0 19 15 29 38 43 Vl 0 19