第七章 图—例题与习题.

《第七章 图—例题与习题.》由会员分享，可在线阅读，更多相关《第七章 图—例题与习题.（15页珍藏版）》请在文档大全上搜索。

1、第七章 图已知一有向图的邻接表存储结构如图所示，分别给出从顶点v1出发进行深度优先和广度优先遍历所得到的顶点序列。第七章 图 5 3 4 5 2 4 2 4 1 4 3 2 第七章 图解：根据有向图的深度优先遍历算法，从顶点v1出发所得到的顶点序列是： v1，v3，v4，v5，v2 根据有向图的广度优先遍历算法，从顶点v1出发所得到的顶点序列是： v1，v3，v2，v4，v5第七章 图有n个顶点的无向图或有向图采用邻接矩阵和邻接表表示，请回答下列问题: (1) 如何计算图中有多少条边？(2) 如何判断任意两个顶点i和j是否有边相连？(3) 如何计算任意一个顶点的度是多少？第七章 图解：(1)

2、对于无向图邻接矩阵中“1”的个数除2为图的边数。邻接表中的各单链表中的结点数除2为图的边数。 对于有向图邻接矩阵中“1”的个数为图的边数。邻接表中的各单链表中的结点数为图的边数。(2) 对于无向图，在邻接矩阵中第i行第j列元素为“1”，或者第j行第i列元素为“1”，则顶点i与j有边相连。在邻接表中的第i个单链表中有结点为j，或者第j个单链表中有结点为i，则顶点i与j有边相连。第七章 图 对于有向图，在邻接矩阵中第i行第j列元素为“1”，则有一条从i到j的边。在邻接表中的第i个单链表中有结点为j，则有一条从i到j的边。(3)对于无向图邻接矩阵中第i行的元素之和为i顶点的度，邻接表中的第i个单链表

3、中的结点数为i顶点的度。 对于有向图邻接矩阵中第i行元素之和为i顶点的入度，第j列元素之和为j顶点的出度。在邻接表中，第i个单链表的结点数就是i顶点的出度，整个邻接表中具有的结点为i的结点数就是i顶点的入度。 返回第七章 图一、基本知识题1. 图的逻辑结构特点是什么？什么是无向图和有向图？什么是子图？什么是网络？2. 什么是顶点的度？什么是路径？什么是连通图和非连通图？什么是非连通图的连通分量？3. 给出图所示的无向图G的邻接矩阵和邻接表两种存储结构。第七章 图 第七章 图4. 假设图的顶点是A、B请根据下面的邻接矩阵画出相应的无向图或有向图。0111101111011110010100000

4、1100010100000110(a)(b)第七章 图5. 分别给出图所示G图的深度优先搜索和广度优先搜索得到的顶点访问序列。 0 第七章 图6. 应用prim算法求图所示带权连通图的最小生成树。 1 1 2 2 2 3 5 3 第七章 图7. 写出图所示有向图的拓扑排序序列。 第七章 图二、算法设计题1. 如图所示图G，试给出其对应的邻接表，并写出深度优先算法。2. 如图所示图G，试给出其对应的邻接矩阵，并写出广度优先算法。3. 编写一个函数通过与用户交互建立一个有向图的邻接表。4. 编写一个无向图的邻接矩阵转换成邻接表的算法。第七章 图 第七章 图5. 已知一个有n个顶点的有向图的邻接表，设计算法分别实现1) 求出图中每个顶点的出度。2) 求出图中每个顶点的入度。3) 求出图中出度最大的一个顶点，输出其顶点序号。4) 计算图中出度为0的顶点个数。返回