数据结构习题解答参考第8章

8入了生成树与生成森林的概念。对于带权图，给出了最小生成树的两种方法：Prim算法和Kruskal算法后者使用了最小堆和并查集作为它的辅助求解在解决最短路径问题时，PrimKruskal方求解最小生成树的Kruskaldijkstra算法，注意dist为防止重复已经过的顶点，需要设置一个标志数组visited对于连通网络、可用不会构成环路的权值最小的n-1会画出用KruskalPrim6n(n-1)/2。1个顶点的

2 3个顶点的

4 5个顶点的ijjin(n-1)/2条边。ADADBECFCC→F，C→F→E。DD→B，D→B→C，D→B→C→F，D→ADADBECF

0 0 0Edge0 0A11B22C5∧0A11B22C5∧3D14∧4E∧5F4∧0A∧1B03∧2C3D4E35∧5F

0 0 00 3∧4∧1∧01∧0∧12∧一个图中有1000个顶点，其邻接矩阵中的矩阵元素有10002 nn个顶点的有向强连通图至少有多少条nn-1nnn10ij之间是否有边相连？任意一个顶点的度是多少？A[i][j]不为零，说明顶②①③④②①③④⑤③④ ③④ ① 操作时，时间代价是O(n*e)？还是O(n+e)O(max(n,e))？需要对所有的顶点一次，所以时间代价是O(n+e)。⑨⑧8-11右图是通图，请画⑨⑧⑩① ⑩①

⑩① ⑩① (1,103,44,55,6)。从③的子孙结点⑩到③的祖先结点①引一 8-15Dijkstra算法计算得到的从顶点①(A)到其它各个顶点的最短路径和最AA5522D2E源点终点AB源点终点ABCDEG=（V，E有nn≥1)n-1有nn≥1)n在AOE(1) (2)(3)(4)(5)(6)(7)(8)(9) (10)(11)(12)(13)(14)(15) 倍在一个具有n个顶点的无向完全图中，包含有 在一个具有n个顶点的无向图中，要连通所有顶点则至少需 条边 对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边 对于一个具有n个顶点和e条边的有向图和无向图，若采用邻接多重表表示，则存 对于一个具有n个顶点和e条边的无向图，当分别采用邻接矩阵、邻接表和邻接多 假定一个图具有n个顶点和e条边，则采用邻接矩阵、邻接表和邻接多重表表示 对于一个具有n个顶点和e (2)n(n-1)/2,n(n-(3)n- (4)邻接矩阵,邻接表,(5) (6)e,(7)出边,入 (8)2n,n,(9)O(n),O(e/n), (10)O(n2),O(n+e),(11)O(n2), (12)n,n-采用邻接表的图的深度优先遍历算法类似于二叉树的（A采用邻接表的图的广度优先遍历算法类似于二叉树的（ 复杂性为（C ，利用Kruskal算法产生最小生成树，其时间复杂性为（D 设图中有n个顶点和e条边，进行深度优先搜索的时间复杂度至多为（E 行广度优先搜索的时间复杂性至多为（F 对于一个具有n个顶点和e条边的无向图进行拓扑排序时总的时间（ (4)判断有向图是否存在回路，除了可以利用拓扑排序方法外，还可以利用（H AB②③④C,D：①②③④E,F：①②③④G：①n ②n+1 ③n-1 ④n+eH：①求关键路径的方法 ②求最短路径的Dijkstra方法③深度优先遍历算 ④广度优先遍历算 610515726105157235364245(始顶点号，终顶点号，权值(,,)(,,)(,,)(,,)(,,)(1)选出的边顺序为:始顶点号，终顶点号，权值(0,3,1)，(3,5,4)，(5,2,2)，(3,4,5)(3,1,5)，(4,1,3)，(1,4,3nijij之间用边连接，边上的权值wijn