计算机网络课件

8-1 已知图G=(V,E)，其中V={a,b,c,d,e,f,g}，E={，，，，，，，，，，，}，请画出图G，并画出图G的邻接矩阵和图G的邻接表。

8-2 对于图8-17所示的有向图，要求给出：

（1）该有向图的邻接矩阵存储结构；

（2）该有向图的邻接表存储结构；

（3）设顶点A为访问的第一个顶点，按照邻接矩阵存储结构给出的每个顶点的邻接顶点次序，给出该有向图的深度优先遍历的顶点访问序列。

（4）设顶点A为访问的第一个顶点，按照邻接矩阵存储结构给出的每个顶点的邻接顶点次序，给出该有向图的广度优先遍历的顶点访问序列。

图8-17 有向图

8-3 对于图8-18所示的无向带权图，要求：

（1）根据普里姆算法思想，画出构造该无向带权图最小生成树的过程；

（2）根据克鲁斯卡尔算法思想，画出构造该无向带权图最小生成树的过程。

3

4

2

7

9

1

8

5

4

9

8

6

1

图8-18 无向带权图

8-4 对于图8-19所示的有向带权图，根据狄克斯特拉算法思想，画出生成从顶点A到其余各顶点最短路径的过程。

25

16

10

10

7

3

12

2

12

8

4

8-19有向带权图

复杂概念题：

8-5 证明：无向完全图中一定有n(n - 1) / 2条边。

8-6 证明：有向完全图中一定有n(n - 1)条弧。

*8-7 证明：在一个有n个顶点的完全图中生成树的数目可以有2n - 1 – 1个。

*8-8 证明：对于一个无向图G = (V, E)，若G中各顶点的度均大于或等于2，则G中必存在回路。

算法设计题：

8-9 编写函数，求邻接矩阵存储结构的有向图G中各顶点的入度。

8-10 编写函数，求邻接矩阵存储结构的有向图G中各顶点的出度。

*8-11 要求：

（1）给出图的非递归的深度优先遍历算法步骤。

（2）设图G采用邻接表存储结构存储，编写一个非递归的深度优先遍历函数。

*8-12 编写实现在邻接表存储的图G中删除顶点v的函数。

（提示：删除一个顶点时要删除和该顶点有关联的所有边）

*8-13 编写函数，判断邻接矩阵存储结构的有向图G中，两个顶点v1和v2之间是否存在从v1到v2的路径。

（提示：利用深度优先遍历函数或广度优先遍历函数）

上机实习题：

8-14 邻接表存储结构图的程序设计。要求：

（1）以图8-17为例，设计一个测试8.3.2节讨论的邻接表存储结构下图的操作函数的主函数，并给出程序运行的输出结果。

（2）设计邻接表存储结构下图的深度优先搜索遍历函数和广度优先搜索遍历函数，并以图8-17为例，编写主函数测试这些函数。

*（3） 编写删除图G中顶点v的函数（提示：删除一个顶点时要删除和该顶点有关联的所有边），并测试该函数的正确性。