数据结构书本习题答案(续)(20201103040933).docxVIP

7.5对n个顶点的无向图和有向图，采用邻接矩阵和邻接表表示时，如何判别下列有关问题 ？ （1） 图中有多少条边？ （2） 任意两个顶点i和j是否有边相连？ （3） 任意一个顶点的度是多少 ？ 答：对于n个顶点的无向图和有向图，用邻接矩阵表示时： （1）设m为矩阵中非零元素的个数 无向图的边数=m/2 有向图的边数=m ⑵无论是有向图还是无向图，在矩阵中第 i行,第j列的元素若为非零值，则该两顶点有边相连。 ⑶对于无向图，任一顶点i的度为第i行中非零元素的个数。 对于有向图，任一顶点i的入度为第i列中非零元素的个数，岀度为第 i行中非零元素的个数，度为入度岀度之和。 当用邻接表表示时： （1）对于无向图，图中的边数=边表中结点总数的一半。 对于有向图，图中的边数=边表中结点总数。 ⑵对于无向图，任意两顶点间是否有边相连，可看其中一个顶点的邻接表，若表中的 adjvex域有另一顶点位置的结点， 则表示有边相连。 对于有向图，则表示有岀边相连。 （3）对于无向图，任意一个顶点的度则由该顶点的边表中结点的个数来决定。 对于有向图，任意一个顶点的岀度由该顶点的边表中结点的个数来决定，入度则需遍历各顶点的边表。 （用逆邻接表可 容易地得到其入度。） 7.6 n个顶点的连通图至少有几条边 ？强连通图呢？ 答：n个顶点的连通图至少有 n-1条边，强连通图至少有 2（n-1）条边。 7.7 DFS和BFS遍历各采用什么样的数据结构来暂存顶点 ？当要求连通图的生成树的高度最小， 应采用何种 遍历？ 答:采用DFS遍历采用栈来暂存顶点。BFS遍历。BFS采用队列来暂存顶点。当要求连通图的生成树的高度最小时，应7 答: 采用 DFS遍历采用栈来暂存顶点。 BFS遍历。 BFS采用队列来暂存顶点。当要求连通图的生成树的高度最小时，应 7. 8 0V5 0￥8 7.9 按顺序输入顶点对：（1，2），（1，6），（2，6），（1，4），（6，4），（1，3），（3，4）,（6，5），（4，5），（1,5）,（3,5）, 根 据第7.2.2节中算法CreatALGraph画出相应的邻接表。并写出在该邻接表上，从顶点 4开始有哪些信誉好的足球投注网站所得的DFS和 BFS序列， 及DFS和BFS生成树。 答：相应的邻接表如下： 2 I AI2I 2 I I 6 I I 1 I A 2 I AI 2I 2 I I 6 I I 1 I A I I~II I—II I 3 I I 5 I I I~II I—II I 4 I I 5 I I I~II I—II I 5 I I 3 I I I~II I—II I 6 I I 5 I I I I I I I I 1 —1―I 1 1 1 6 I —T | 1 I A I I~1―I I~1I 4 I —T | 6 I A I I~1―I I~1I 2 I —T | 1 I A I 1 1 1 1 I I I—II 1 I 」I I—II I —T I 根据上面的邻接表画岀的图见下图 OTL?9dL01d 4 12 6 5 3 2 d BFE室成樹 DFS 序列是：453162BFS 序列是：453612 DFS 序列是：453162 BFS 序列是：453612 7.10什么样的图其最小生成树是唯一的 ？用PRIM和Kruskal求最小生成树的时间各为多少 ？它们分别适合 于哪类图？ 答：当候选轻边集中的轻边数始终等于 1条时，其最小生成树是唯一的。用 Prim和Kruskal求最小生成树 的时间复杂度分别为 0(n2)和O(elge),前者适合于稠密图，后者适合于稀疏图 ? 7.11对图7.26 (下图)所示的连通图，请分别用 Prim和Kruskal算法构造其最小生成树。 答: 答: 7.13试写出图7.28(下图)所示有向图的所有拓扑序列，并指出就用 7.6节给出的NonPreFirstTopSort 算法求得的是哪个 序列，设邻接表的边表结点中的邻接点序号是递增有序的。 vO vO v2 答：上图中所有拓扑序列如下： v0v1v5v2v3v6v4 * v0v1v5v2v6v3v4 v0v1v5v6v2v3v4 v1v0v5v6v2v3v4 v1v0v5v2v3v6v4 v1v0v5v2v6v3v4 v1v5v0v2v3v6v4 v1v5v0v2v6v3v4 v1v5v0v6v2v3v4 v5v1v0v2v3v6v4 v5v1v0v2v6v3v4 v5v1v0v6v2v3v4 v5v0v1v2v3v6v4 v5v0v1v2v6v3v4 v5v0v1v6v2v3v4 v0v5v6v1v2v3v4 v1v5v6v0v2v3v4 v5v6v1v0v2v3v4 v5v6v0v1v2v3v4 v5v0v6v1v2v3v4