第七章 图 名词解释 1.图2.无向完全图3.有向完全图4.子图5.连通分量6.图的遍历 7.图的最小生成树8.拓扑排序 填空题 1.设x,y是图G中的两顶点,则(x,y)与(y,x)被认为 边,但与是 的两条弧 2.若顶点的偶对是有序的,此图为 图,有序偶对用 括号括起来:若顶点偶 对是无序的,此图为 图,无序偶对用 括号括起来 3.设x,y∈V,若∈E,则表示有向图G中从x到y的一条 称为 点,y称为 点。若(x,y)∈E,则在无向图G中x和y间有一条 4.在无向图中,若顶点x与y间有边(x,y),则x与y互称 边(x,y)称为与顶点 和 5.一个具有n个顶点的完全无向图的边数为 。一个具有n个顶点的完全有向图的弧 度数为 6.图的边或弧附带的数值叫 每条边或弧都带权的图称为 或 7.无向图中的顶点V的度是 记为 若G是一个有向图,则把以顶点V为 终点的弧的数目称为V的 记为 把以顶点V为始点的弧的数目称为V的 称为。有向图中顶点V的度定义为D(V)= 8.路径长度定义为 。第一个顶点和最后一个顶点相同的路径称为 序列中顶点不重复出现的路径称为 除了第一个顶点和最后一个顶点外 其余顶点不重复的回路,称为 或 9.在无向图中,如果从顶点ⅴ到顶点v’有路径,则称v和v是 的。如果对于图中的 任意两个顶点v,v∈V,且v和v都是连通的,则称G为 10.连通分量是无向图中的 连通子图。 1.一个连通图的生成树是含有该连通图的全部顶点的一个 12.若连通图G的顶点个数为n,则G的生成树的边数为 。如果G的一个子图G的 边数 则G′中一定有环。相反,如果G的边数 则G′一定不连通 13.无向图的邻接矩阵是一个矩阵,有向图的邻接矩阵不一定是矩阵 14.对于无向图的邻接矩阵,顶点vi的度是 对于有向图的邻接矩阵,顶 点vi的出度OD(vi)为 ,顶点vi的入度ID(vi)是 15.图的存储结构主要有 和 两种。 16.邻接表表示法是借助 来反映顶点间的邻接关系,所以称这个单链表为邻接表。 17.对无向图,若它有n顶点e条边,则其邻接表中需要 个结点。其中, 个结点构成邻接表 个结点构成顶点表。 8.对有向图,若它有n顶点e条边,则其邻接表中需要 个结点。其中, 个结点构成邻接表 个结点构成顶点表。 19.在邻接表上,无向图中顶点vi的度恰为 对有向图,顶点v的出度是 为了求入度,必须遍历整个邻接表,在所有单链表中,其邻接点域的值 为 的结点的个数是顶点vi的入度。 0.遍历图的基本方法有 优先搜索和 优先搜索两种 21.以下是图的深度优先算法,请在 处填充适当的语句
1 第七章 图 一、名词解释 1.图 2.无向完全图 3.有向完全图 4.子图 5.连通分量 6.图的遍历 7.图的最小生成树 8.拓扑排序 一、填空题 1.设 x,y 是图 G 中的两顶点，则（x,y）与（y,x）被认为________边，但与是________ 的两条弧。 2.若顶点的偶对是有序的，此图为________图，有序偶对用________括号括起来；若顶点偶 对是无序的，此图为________图，无序偶对用________括号括起来。 3.设 x,y∈V，若∈E,则表示有向图 G 中从 x 到 y 的一条________，x 称为________ 点，y 称为________点。若（x,y）∈E，则在无向图 G 中 x 和 y 间有一条________。 4.在无向图中，若顶点 x 与 y 间有边（x,y），则 x 与 y 互称________，边（x,y）称为与顶点 x 和 y________。 5.一个具有 n 个顶点的完全无向图的边数为________。一个具有 n 个顶点的完全有向图的弧 度数为________。 6.图的边或弧附带的数值叫________。每条边或弧都带权的图称为________或________。 7.无向图中的顶点 V 的度是________，记为________。若 G 是一个有向图，则把以顶点 V 为 终点的弧的数目称为 V 的________，记为________；把以顶点 V 为始点的弧的数目称为 V 的 ________，称为________。有向图中顶点 V 的度定义为 D（V）=________。 8.路径长度定义为________。第一个顶点和最后一个顶点相同的路径称为________或 ________。序列中顶点不重复出现的路径称为________。除了第一个顶点和最后一个顶点外， 其余顶点不重复的回路，称为________或________。 9.在无向图中，如果从顶点 v 到顶点 v’有路径，则称 v 和 v’是_______的。如果对于图中的 任意两个顶点 vi,vj∈V，且 vi 和 vj 都是连通的，则称 G 为________。 10.连通分量是无向图中的________连通子图。 11.一个连通图的生成树是含有该连通图的全部顶点的一个________。 12.若连通图 G 的顶点个数为 n，则 G 的生成树的边数为________。如果 G 的一个子图 G’的 边数________，则 G’中一定有环。相反，如果 G’的边数________，则 G’一定不连通。 13.无向图的邻接矩阵是一个________矩阵，有向图的邻接矩阵不一定是________矩阵。 14.对于无向图的邻接矩阵，顶点 vi 的度是________________。对于有向图的邻接矩阵，顶 点 vi 的出度 OD（vi）为________________，顶点 vi 的入度 ID(vi)是________________。 15.图的存储结构主要有________和________两种。 16.邻接表表示法是借助________来反映顶点间的邻接关系，所以称这个单链表为邻接表。 17.对无向图，若它有 n 顶点 e 条边，则其邻接表中需要________个结点。其中，________ 个结点构成邻接表，________个结点构成顶点表。 18.对有向图，若它有 n 顶点 e 条边，则其邻接表中需要________个结点。其中，________ 个结点构成邻接表，________个结点构成顶点表。 19.在邻接表上，无向图中顶点 vi 的度恰为________________。对有向图，顶点 vi 的出度是 ________________。为了求入度，必须遍历整个邻接表，在所有单链表中，其邻接点域的值 为________的结点的个数是顶点 vi 的入度。 20.遍历图的基本方法有________优先搜索和________优先搜索两种。 21.以下是图的深度优先算法，请在________处填充适当的语句
Dfs(GraphTp g, int v) I ArcNodeTp * p printf (%d", v) visited[v]=1 while(p!=NULL) lif( Dfs(g, p->ad jvex) 22.以下是图的广度优先搜索算法,请在处填充适当的语句 Bfs(GraphTp g, int v) [Queptrtp Q ArcNodeTp *p InitQueue(&Q) printf(n%d", v) visited[v]=1 hile(! EmptyQueue(Q)) p=g adjlist[].firstarc while(p! =NULL lif(!visited [p->adjvex]) Printf("%d", p->>adjvex) visited[[-adjvex]=1 EnQueue(&Q, p->ad jvex) 23.深度优先搜索遍历类似于树的 遍历,它所用到的数据结构是:广~度优先 搜索遍历类似于树的遍历,它所用到的数据结构是 24.任何连通图的连通分量只有一个,即 25对具有n个顶点的图其生成树有且仅有条边,即生成树是图的边数 的连 通图 26.一个图的的表示法是惟一的,而表示法是不惟一的 27.对无向图,其邻接矩阵是一个关于 对称的矩阵 8.在有向图的邻接矩阵上,由第i行可得到第 个结点的出度,而由第j列可得到第 个结点的入度 的有向图,其全部顶点有可能排成一个拓扑序列 30.一个有向图G中若有弧,、和,则在图G的拓扑序列中,顶点V、V 和V的相对位置为 单项选择题
2 Dfs(GraphTp g,int v) { ArcNodeTp *p; printf(“%d”,v); visited[v]=1; p=________________; while(p!=NULL) {if(!________________) Dfs(g,p->adjvex); p=________________; } } 22.以下是图的广度优先搜索算法，请在________处填充适当的语句。 Bfs(GraphTp g,int v) {QueptrTp Q; ArcNodeTp *p; InitQueue(&Q); printf(“%d”,v); visited[v]=1; ________________ while(!EmptyQueue(Q)) {________________; p=g.adjlist[v].firstarc; while(p!=NULL) {if(!visited[p->adjvex]) {printf(“%d”,p->>adjvex); visited[[->adjvex]=1; EnQueue(&Q,p->adjvex); } ________________; } } } 23.深度优先搜索遍历类似于树的________遍历，它所用到的数据结构是________；广度优先 搜索遍历类似于树的________遍历，它所用到的数据结构是________。 24.任何连通图的连通分量只有一个，即________。 25.对具有 n 个顶点的图其生成树有且仅有________条边，即生成树是图的边数________的连 通图。 26.一个图的________的表示法是惟一的，而________表示法是不惟一的。 27.对无向图，其邻接矩阵是一个关于________对称的矩阵。 28.在有向图的邻接矩阵上，由第 i 行可得到第________个结点的出度，而由第 j 列可得到第 ________个结点的入度。 29.________的有向图，其全部顶点有可能排成一个拓扑序列。 30.一个有向图 G 中若有弧,、和,则在图 G 的拓扑序列中，顶点 Vi、Vj 和 Vk 的相对位置为________。 二、单项选择题
1.设有无向图G=(V,E)和G′=(V,E),如G′为G的生成树,则下面不正确的说法是( ①G’为G的子图 ②G’为G的连通分量 ③G’为G的极小连通子图且V ④G’是G的无环子图 2.任何一个带权的无向连通图的最小生成树( ①只有一棵②有一棵或多棵③一定有多棵④可能不存在 3.设图G采用邻接表存储,则拓扑排序算法的时间复杂度为() ①0(n)②0(n+e) 0(n*n)④0(n*e) 4.含n个顶点的连通图中的任意一条简单路径,其长度不可能超过 ②n/2③n-1④n V2∧ 图单项选择题5 图单项选择愚以 5.一有向图G的邻接表存储结构如图单项选择5所示。现按深度优先遍历算法,从顶点Ⅵ1 出发,所得到的顶点序列是 () ②V,V3,V,V2,V5③V1,V2,V,V,V5④V1,V,V,V5,V2 6.在无向图中,所有顶点的度数之和是所有边数的()倍。 ①0.5 ③ 7.在有向图中,所有顶点的入度之和是所有顶点出度之和的()倍。 ①0.5 8.在图的邻接表存储结构上执行深度优先搜索遍历类似于二叉树上的 ①先根遍历 ②中根遍历 ③后根遍历 ④按层次遍历 9.在图的邻接表存储结构上执行广度优先搜索遍历类似于二叉树上的 ①先根遍历 ②中根遍历 ③后根遍历 ④按层次遍历 0.判断一个有向图是否存在回路,除了可以利用拓扑排序方法,还可以利用 ①求关键路径方法②求最短路径的 Di jkstra方法③广度优先遍历方法④深度优先遍历方法 11.在图单项选择中,从顶点V1出发,按广度优先遍历图的顶点序列是 oV1V3VsV4V2V6V②V1V2V4VnV6VsV3③V1V5V3V4V2VV6④VV4VnV2V6V5V3 12.在图单项选择中,从顶点V1出发,广度遍历图的顶点序列是 ①V1V5V3V4V2V6V7②VV5V3V4V2V7V③V1VV2V6VV5V3④V1V2V4VV6VV3 13.设有6个结点的无向图,该图至少应有()条边能确保是一个连通图 ①5 ②6 ③7 ④8 4.以下说法正确的是 ①连通图的生成树,是该连通图的一个极小连通子图。 ②无向图的邻接矩阵是对称的,有向图的邻接矩阵一定是不对称的 ③任何一个有向图,其全部顶点可以排成一个拓扑序列。 ④有回路的图不能进行拓扑排序 15以下说法错误的是 ①用相邻矩阵法存储一个图时,在不考虑压缩存储的情况下,所占用的存储空间大小只与图 3
3 1.设有无向图 G=（V，E）和 G’=（V’,E’）,如 G’为 G 的生成树，则下面不正确的说法是（ ） ①G’为 G 的子图 ②G’为 G 的连通分量 ③G’为 G 的极小连通子图且 V’=V ④G’是 G 的无环子图 2.任何一个带权的无向连通图的最小生成树（ ） ①只有一棵 ②有一棵或多棵 ③一定有多棵 ④可能不存在 3.设图 G 采用邻接表存储，则拓扑排序算法的时间复杂度为（ ） ①O(n) ②O(n+e) ③O(n*n) ④O(n*e) 4.含 n 个顶点的连通图中的任意一条简单路径，其长度不可能超过 （ ） ①1 ② n/2 ③ n-1 ④n 5．一有向图 G 的邻接表存储结构如图单项选择 5 所示。现按深度优先遍历算法，从顶点 V1 出发，所得到的顶点序列是 （ ） ①V1,V3, V2 ,V4, V5 ②V1, V3, V4, V2, V5 ③V1,V2, V3, V4, V5 ④V1, V3, V4, V5 , V2 6.在无向图中，所有顶点的度数之和是所有边数的（ ）倍。 ①0.5 ②1 ③2 ④4 7.在有向图中，所有顶点的入度之和是所有顶点出度之和的（ ）倍。 （ ） ①0.5 ② 1 ③ 2 ④4 8．在图的邻接表存储结构上执行深度优先搜索遍历类似于二叉树上的 （ ） ①先根遍历 ② 中根遍历 ③ 后根遍历 ④按层次遍历 9．在图的邻接表存储结构上执行广度优先搜索遍历类似于二叉树上的 （ ） ①先根遍历 ②中根遍历 ③后根遍历 ④按层次遍历 10．判断一个有向图是否存在回路，除了可以利用拓扑排序方法，还可以利用 （ ） ①求关键路径方法②求最短路径的 Dijkstra 方法③广度优先遍历方法④深度优先遍历方法 11．在图单项选择中，从顶点 V1 出发，按广度优先遍历图的顶点序列是 （ ） ①V1 V3 V5 V4 V2 V6 V7 ②V1 V2 V4 V7 V6 V5 V3 ③V1 V5 V3 V4 V2 V7 V6 ④V1 V4 V7 V2 V6 V5 V3 12.在图单项选择中，从顶点 V1 出发,广度遍历图的顶点序列是 （ ） ①V1 V5 V3 V4 V2 V6 V7 ②V1 V5 V3 V4 V2 V7 V6 ③V1 V7 V2 V6 V4 V5 V3 ④V1 V2 V4 V7 V6 V5 V3 13.设有 6 个结点的无向图，该图至少应有（ ）条边能确保是一个连通图。 （ ） ① 5 ② 6 ③ 7 ④ 8 14.以下说法正确的是 （ ） ①连通图的生成树，是该连通图的一个极小连通子图。 ②无向图的邻接矩阵是对称的，有向图的邻接矩阵一定是不对称的。 ③任何一个有向图，其全部顶点可以排成一个拓扑序列。 ④有回路的图不能进行拓扑排序。 15 以下说法错误的是 （ ） ①用相邻矩阵法存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图
中结点个数有关,而与图的边数无关 ②邻接表法只能用于有向图的存储,而相邻矩阵法对于有向图和无向图的存储都适用 存储无向图的相邻矩阵是对称的,因此只要存储相邻矩阵的下(或上)三角部分就可以了 ③用相邻矩阵A表示图,判定任意两个结点V和Ⅴ之间是否有长度为m的路径相连,则只 要检查A的第i行第j列的元素是否为0即可 16.以下说法正确的是 ①连通分量是无向图中的极小连通子图。 ②强连通分量是有向图中的极大强连通子图。 ③在一个有向图的拓扑序列中,若顶点a在顶点b之前,则图中必有一条弧。 ④对有向图G,如果从任意顶点出发进行一次深度优先或广度优先搜索能访问到每个顶点,则 该图一定是完全图。 四、简答及应用 1.简述图的邻接矩阵表示的类型定义 2.简述图的邻接表的类型定义 3.给出无向图简答题3中g1的邻接矩阵和邻接表 图简答题3 4.分别给出图简答题3中g2的邻接矩阵、邻接表和逆邻接表。 5.分别给出图简答题3中g从巧出发按深度优先搜索和广度优先搜索算法遍历得到的顶点 序列。 求出图简答题6-1的连通分量。 成⑧ 图简答题6-1 7.求出带权图简答题7-1的最小生成树 写出有向图简答题8-1的拓扑排序序列 9.给出网图简答题9-1的邻接矩阵表示 10.已知连通网的邻接矩阵如下,试画出它所表示的连通网及该连通网的最小生成树
4 中结点个数有关，而与图的边数无关。 ②邻接表法只能用于有向图的存储，而相邻矩阵法对于有向图和无向图的存储都适用。 ③存储无向图的相邻矩阵是对称的，因此只要存储相邻矩阵的下（或上）三角部分就可以了 ③用相邻矩阵 A 表示图，判定任意两个结点 Vi 和 Vj 之间是否有长度为 m 的路径相连，则只 要检查 A 的第 i 行第 j 列的元素是否为 0 即可。 16．以下说法正确的是 （ ） ①连通分量是无向图中的极小连通子图。 ②强连通分量是有向图中的极大强连通子图。 ③在一个有向图的拓扑序列中，若顶点 a 在顶点 b 之前，则图中必有一条弧。 ④对有向图 G,如果从任意顶点出发进行一次深度优先或广度优先搜索能访问到每个顶点，则 该图一定是完全图。 四、简答及应用 1． 简述图的邻接矩阵表示的类型定义 2． 简述图的邻接表的类型定义。 3． 给出无向图简答题 3 中 g1 的邻接矩阵和邻接表。 4．分别给出图简答题 3 中 g2 的邻接矩阵、邻接表和逆邻接表。 5．分别给出图简答题 3 中 g3 从 v5 出发按深度优先搜索和广度优先搜索算法遍历得到的顶点 序列。 6．求出图简答题 6-1 的连通分量。 7．求出带权图简答题 7-1 的最小生成树 8．写出有向图简答题 8-1 的拓扑排序序列。 9．给出网图简答题 9-1 的邻接矩阵表示。 10．已知连通网的邻接矩阵如下，试画出它所表示的连通网及该连通网的最小生成树
128 59∞∞斗 10x24 田简衍题9-1 对于图简答题11-1从其邻接表中回答下列问题: (1)图中有多少条弧? (2)图中是否存在从i到j的弧? (3)如何求顶点i的出度? 图简题11-1 图簡苍题13·1 12.图简答题11-1所示为一有向图,请给出该图的下述要求: (1)每个顶点的入/出度 (2)邻接矩阵 (3)邻接表。 (4)逆邻接表 13.拓扑排序的结果不是唯一的,对图简答题13-1进行拓扑排序,试写出其中任意5个不同 的拓扑排序列。 14.对m个顶点的无向图G,采用邻接矩阵,如何判别下列有关问题 (1)图中有多少条边? (2)任意两个顶点i和j是否有边相连? (3)任意一个顶点的度是多少? 15.已知图G的邻接表如图简答题15-1所试,顶点Ⅵ1为出发点,完成要求 (1)深度优先搜索的顶点序列 (2)广度优先搜索的顶点序列 (3)由深度优先搜索得到的一棵生成树 (4)由广度优先搜索得到的一棵生成树。 Vertex f
5 11．对于图简答题 11-1 从其邻接表中回答下列问题： （1） 图中有多少条弧？ （2） 图中是否存在从 i 到 j 的弧？ （3） 如何求顶点 i 的出度？ 12．图简答题 11-1 所示为一有向图，请给出该图的下述要求： （1） 每个顶点的入/出度。 （2） 邻接矩阵。 （3） 邻接表。 （4） 逆邻接表。 13．拓扑排序的结果不是唯一的，对图简答题 13-1 进行拓扑排序，试写出其中任意 5 个不同 的拓扑排序列。 14．对 m 个顶点的无向图 G，采用邻接矩阵，如何判别下列有关问题： （1） 图中有多少条边？ （2） 任意两个顶点 i 和 j 是否有边相连？ （3） 任意一个顶点的度是多少？ 15.已知图 G 的邻接表如图简答题 15-1 所试，顶点 V1 为出发点，完成要求： （1） 深度优先搜索的顶点序列； （2） 广度优先搜索的顶点序列； （3） 由深度优先搜索得到的一棵生成树； （4） 由广度优先搜索得到的一棵生成树。 Vertex fi
-4M 1A 图简答题15 16.设有一无向图G=(V,E),其中 V={1,2,3,4,5,6},E={(1,2),(1,6),(2,6),(1,4),(6,4),(1,3),(3,4),(6,5),(4,5),(1,5),( 3,5)} (1)按上述顺序输入后,画出其相应的邻接表 (2)在该邻接表上,从顶点4开始,写出DFS序列和BFS序列 17.图简答题17-1所示为一无向连通网络,先要求根据prim算法构造出它的最小生成树 图简答题17-1 五、算法设计 1.写出将一个无向图的邻接矩阵转换成邻接表的算法。 2.写出将一个无向图的邻接表转换成邻接矩阵的算法。 3.试以邻接矩阵为存储结构,分别写出连通图的深度优先和广度优先搜索算法 4.写出建立一个有向图的逆邻接表的算法。 5.G为一n个顶点的有向图,其存储结构分别为 (1)邻接矩阵 (2)邻接表。 请写出相应存储结构上的计算有向图G出度为0的顶点个数的算法 6.以邻接表作存储结构,给出拓扑排序算法的实现。 6
6 16.设有一无向图 G=(V,E),其中 V={1,2,3,4,5,6},E={(1,2),(1,6),(2,6),(1,4),(6,4),(1,3),(3,4),(6,5),(4,5),(1,5),( 3,5)}。 （1） 按上述顺序输入后，画出其相应的邻接表； （2） 在该邻接表上，从顶点 4 开始，写出 DFS 序列和 BFS 序列。 17．图简答题 17-1 所示为一无向连通网络，先要求根据 prim 算法构造出它的最小生成树。 五、算法设计 1． 写出将一个无向图的邻接矩阵转换成邻接表的算法。 2． 写出将一个无向图的邻接表转换成邻接矩阵的算法。 3． 试以邻接矩阵为存储结构，分别写出连通图的深度优先和广度优先搜索算法。 4． 写出建立一个有向图的逆邻接表的算法。 5． G 为一 n 个顶点的有向图，其存储结构分别为： （1） 邻接矩阵； （2） 邻接表。 请写出相应存储结构上的计算有向图 G 出度为 0 的顶点个数的算法。 6．以邻接表作存储结构，给出拓扑排序算法的实现