11111111125125333434343456426426426

2、设一个无向图的邻接矩阵如下图所示： （1）画出该图；

（2）画出从顶点0出发的深度优先生成树；

?01110?10100??11011??10101?00110??00011?0100?0??0?? 1?1??0??答案： (1)图形态 (2)深度优先搜索树

132325454

43、写出下图中全部可能的拓扑排序序列。

15236 答案：1，5，2，3，6，4 1，5，6，2，3，4 5，1，2，3，6，4

5，1，6，2，3，4 5，6，1，2，3，4 4、AOE网G如下所示，求关键路径。（要求标明每个顶点的最早发生时间和最迟发生时间，并画出关键路径）

3v0v132v3v42v52324v2 答案：(1)最早发生时间和最迟发生时间： (2)关键路径：

顶点v0v1v2v3v4v5ve032668vl032668v023v13v42v5v3v242

5、已知有向图G如下所示，根据迪杰斯特拉算法求顶点v0到其他顶点的最短距离。（给出求解过程）

v04v24v32v49512427v1

答案： 终点 v1 v2 v3 v4 vj s 从v0到各终点的d值和最短路径的求解过程 i=1 i=2 i=3 i=4 12 (v0,v1) 12 (v0,v1) 7 (v0,v4,v1) 4 (v0,v2) 9 (v0,v3) 8 7 7 (v0,v2,v3) (v0,v4,v3) (v0,v4,v3) 5 (v0,v4) 5 (v0,v4) v2 v4 v1 v3 {v0,v2} {v0,v4} {v0,v4,v1} {v0,v4,v3} 6、已知图G如下所示，根据Prim算法，构造最小生成树。（要求给出生成过程）

v08v2242v6v3756v448v17v58v7 答案：prim算法求最小生成树如下：

v0v06v44v57v6v06v44v57v22v6v06v44v5v32v22v67v06v44v5v32v22v67v06v45v7v224v5v327v6v06v45v74v17v56v4

7、已知有向图如下所示，请写出该图所有的拓扑序列。

v2v3v1v4v5v8v6v7

答案：拓扑排序如下：

v1, v2, v4, v6, v5, v3, v7, v8 v1, v2, v4, v6, v5, v7, v3, v8 v1, v2, v6, v4, v5, v3, v7, v8 v1, v2, v6, v4, v5, v7, v3, v8 v1, v6, v2, v4, v5, v3, v7, v8 v1, v6, v2, v4, v5, v7, v3, v8 8、如下图所示的AOE网，求：

（1）求事件的最早开始时间ve和最迟开始时间vl；

事件 1 2 3 4 5 6 7 8 9 Ve Vl （2）求出关键路径； V2a1a416a24a35V4a62V6V3a94a51V5a79a87V8a114V9汇点V7a102V1源点

答案：(1)求ve和vl (2)关键路径

事件vevl100*266*346458577*671071616*81414*91818*v16v21v57v849v72v9如下所示的有向图，回答下面问题：

v1v2 （1）该图是强连通的吗？若不是，给出强连通分量。

v4v3（2）请给出图的邻接矩阵和邻接表表示。

答案：(1) 是强连通图 (2) 邻接矩阵和邻接表为：

0010100001011000v1v2v3v4v2v3v1v3v4

??112610??1?89?????9、已知图G的邻接矩阵A=128??2?， 试画出它所表示的图G，并根据Prim??69??4????10?24???算法求出图的的最小生成树（给出生成过程）。

答案：

(1)图形态： (2)prim算法求最小生成树：

v112102v54v3189v4v118v3v5v22v5v324v4v2v11v2v118v3v2v118v2

10、如下图所示的AOV网，写出其中三种拓扑排序序列。

v0v2v1v3v4v5v6v7

11、已知图G如下，根据克鲁斯卡尔算法求图G的一棵最小生成树。（要求给出构造过程）

答案：kruskal算法的最小生成树