数据结构（本）课程辅导与练习-第7章 第7章图 木章概念较多。算法较复桑。但教材中对算法要求根简单，因此重点对概之加以总结： 以帮助同学们理解。 一、相关术语 无向图、有向图、顶点、边、端点、部接点、出边、入边、出边邻接点、入边邻接点， 顶点的度、入度、出度、完全图、剩密图、稀疏图、子图、路径长度、简单草路径、国路、 连通图、连通分量丰连通图，强连通分量，最小生成树： 二、图的二元组定义 图G由两个集合V和E组成，记为： =W,) 其中： ￥是顶点的有穷非空集合， E是V中嘎点偶对（称为边）的有穷集。 通常，也将图G的顶点集和边集分别记为V(G)和E(G),E()可以是空集。若E(G)为空， 则图G只有顶点而没有边。 三、有向图和无向图 1,有向图 若图G中的每条边都是有方向的，则称G为有向图（①i红aph), (1)有向边的表示 在有向图中，一条有向边是由两个顶点组成的有序对，有序对通常用尖括号表示， 有向边也称为弧(c),边的始点称为弧尾(Tail),终点称为头Head)。 【例】《。>表示一条有向边，，是边的始点（起点），是边的终点。因此，《，> 和,<VE v} 1
1 数据结构(本)课程辅导与练习-第 7 章 第 7 章 图 本章概念较多，算法较复杂，但教材中对算法要求很简单，因此重点对概念加以总结， 以帮助同学们理解。 一、相关术语 无向图、有向图、顶点、边、端点、邻接点、出边、入边、出边邻接点、入边邻接点、 顶点的度、入度、出度、完全图、稠密图、稀疏图、子图、路径长度、简单犁路径、回路、 连通图、连通分量 非连通图、强连通分量、最小生成树。 二、图的二元组定义 图 G 由两个集合 V 和 E 组成，记为： G=(V，E) 其中： V 是顶点的有穷非空集合， E 是 V 中顶点偶对(称为边)的有穷集。 通常，也将图 G 的顶点集和边集分别记为 V(G)和 E(G)。E(G)可以是空集。若 E(G)为空， 则图 G 只有顶点而没有边。 三、有向图和无向图 1．有向图 若图 G 中的每条边都是有方向的，则称 G 为有向图(Digraph)。 （1）有向边的表示 在有向图中，一条有向边是由两个顶点组成的有序对，有序对通常用尖括号表示。 有向边也称为弧(Arc)，边的始点称为弧尾(Tail)，终点称为弧头(Head)。 【例】表示一条有向边，vi 是边的始点(起点)，vj 是边的终点。因此， 和是两条不同的有向边。 （2）有向图的表示 【例】下面(a)图中 G1 是一个有向图。图中边的方向是用从始点指向终点的箭头表示 的，该图的顶点集和边集分别为： V(G1)={v1，v2，v3} E(G1)={，，}
V3 (a)GL 2.无向图 若图G中的每条边都是设有方向的，则移G为无向图digraph), (1)无向边的表示 无向图中的边均是顶点的无序对，无序对通常用属括号表示。 【例】无序对(：)和(，)表示同一条边。 (2)无向图的表示 【例】下面(h)图中的G和(c)图中的G均是无向图，它们的顶点集和边集分别为： V(G》=w,v":v E(G=g》,(》,v》,(m》,《s,《v] V(G》=w,rv4,,, E(G=(,,(v》,《av》,(a}。《,()l 03 VE 16 (h)Gz (c）G 注意： 在以下时论中，不考虑面点到其自身的边。即若(，)或《，》是E(G)中的一条 边，则要求≠。此外，不允许一条边在图中重复出现，即贝时论简单的图。 3,图G的项点数n和边数0的关系 (1)若G是无向，则0≤e≤■m-1)2 恰有n(m-1)/2条边的无向图称无向完全图ndireet-ed Complete Graph (2)若G是有向图，则0≤e≤n(m-1) 恰有n(n-l》条边的有向图称为有向完全图(Directed Complete Graph). 注意： 完全图具有最多的边数。任意一对项点问均有边相连。 【例】上面(b)图的G就是风有4个顶点的无向完全图. 四、图的边和顶点的关系 2
2 2．无向图 若图 G 中的每条边都是没有方向的，则称 G 为无向图(Undigraph)。 （1）无向边的表示 无向图中的边均是顶点的无序对，无序对通常用圆括号表示。 【例】无序对(vi，vj)和(vj，vi)表示同一条边。 （2）无向图的表示 【例】下面(b)图中的 G2 和(c)图中的 G3 均是无向图，它们的顶点集和边集分别为： V(G2)={v1，v2，v3，v4} E(G2)={(vl，v2)，(v1，v3)，(v1，v4)，(v2，v3)，(v2，v4)，(v3，v4)} V(G3)={v1，v2，v3，v4，v5，v6，v7} E(G3)={(v1，v2)，(vl，v3)，(v2，v4)，(v2，v5)，(v3，v6)，(v3，v7)} 注意： 在以下讨论中，不考虑顶点到其自身的边。即若(v1，v2)或是 E(G)中的一条 边，则要求 v1≠v2。此外，不允许一条边在图中重复出现，即只讨论简单的图。 3．图 G 的顶点数 n 和边数 e 的关系 （1）若 G 是无向图，则 0≤e≤n(n-1)/2 恰有 n(n-1)/2 条边的无向图称无向完全图(Undireet-ed Complete Graph) （2）若 G 是有向图，则 0≤e≤n(n-1) 恰有 n(n-1)条边的有向图称为有向完全图(Directed Complete Graph)。 注意： 完全图具有最多的边数。任意一对顶点间均有边相连。 【例】上面(b)图的 G2 就是具有 4 个顶点的无向完全图。 四、图的边和顶点的关系
1.无向边和项点美系 若(，v小是一条无向边，则称顶点V,和v,互为邻接点djacent),成称%和，相 邻接：并称(，v)依用或关眠(Incident)于顶点和，或称(：，》与顾点v,和相关眼。 【例】下图G中： ①与顶点相邻接的顶点是和 ②关联于顶点的边是(：)，(v)和：) V?0 )G园 2。有向边和项点美系 若(w,v》是一条有向边，则称顶点%邻接到V,顶点￥，邻接于顶点，：并称边w: v》美联于，和￥，或称(，￥》与顶点，和￥，相关联 【例】在下图G中，关联于顶点%的弧是(w,>,《的，￥>和（的，>。 Va (n)GI 3,顶点的度（①e gree) (1)无向图中项点￥的度(Degree) 无向图中现点￥的度①eee)是关联于该顶点的边的数目，记为D()。 【例】上图G中项点的度为3 (2)有白图顶点v的入度(1 nDegree】 有向图中，以项点v为峰点的边的数目称为？的入度(Indegree),记为D(w)。 【例】上图G中顶点的人度为1 (3)有向图项点v的出度(0 utdegree) 有向图中，以顶点v为始点的边的数目。称为v的出度Outdegree),记为0O(v) 【例】上图中顾点？的出度为2 注意： ①有向图中，现点￥的度定义为该项点的入度和出度之和，即(w)=D(w)+0(w)。 【例】上图G中项点：的人度为1，出度为2。则度为3， ②无论有向图还是无向图，。项点数、边数e和度数之间有如下关系：
3 1.无向边和顶点关系 若(vi,vj)是一条无向边，则称顶点 vi 和 vj 互为邻接点(Adjacent)，或称 vi 和 vj 相 邻接；并称(vi,vj)依附或关联(Incident)于顶点 vi 和 vj，或称(vi，vj)与顶点 vi和 vj 相关联。 【例】下图 G2 中： ① 与顶点 v1 相邻接的顶点是 v2，v3 和 v4 ② 关联于顶点 v2 的边是(v1，v2)，(v2，v3)和(v2，v4) 2．有向边和顶点关系 若是一条有向边，则称顶点 vi 邻接到 vj，顶点 vi 邻接于顶点 vj；并称边关联于 vi 和 vj 或称与顶点 vi和 vj相关联 【例】在下图 G1 中，关联于顶点 v2 的弧是，和。 3．顶点的度(Degree) （1）无向图中顶点 v 的度(Degree) 无向图中顶点 v 的度(Degree)是关联于该顶点的边的数目，记为 D(v)。 【例】上图 G2 中顶点 v1 的度为 3 （2）有向图顶点 v 的入度(InDegree) 有向图中，以顶点 v 为终点的边的数目称为 v 的入度(Indegree)，记为 ID(v)。 【例】上图 G1 中顶点 v2 的人度为 l （3）有向图顶点 v 的出度(Outdegree) 有向图中，以顶点 v 为始点的边的数目，称为 v 的出度(Outdegree)，记为 OD(v) 【例】上图 G1 中顶点 v2 的出度为 2 注意： ①有向图中，顶点 v 的度定义为该顶点的入度和出度之和，即 D(v)=ID(v)+OD(v)。 【例】上图 G1 中顶点 v2 的人度为 l，出度为 2，则度为 3。 ②无论有向图还是无向图，顶点数 n、边数 e 和度数之间有如下关系：
五、子图 设，回是一个图。若V是V的子集，E是E的子集，且E旷中的边所关联的项点 均在V'中，则G=(W,E)也是一个图。并称其为G的子图(Subgraph)。 【例】下图给出了有向图G的若干子图：图7,3给出了无向图Ga的若干个子图。 (n)GL V:d ● (b)G2 作不干子图 注意： 设V={,,,E={(,),(。v}。显然，V”属于VG》,E属于EG》,国 因为E中序得对(w,v小所关联的顶点，不在V'中，所以，E)不是图，也就不可能是 Ga的子图。 六、略径Path) 1,无向图的路径 在无向图G中，若存在一个顶点序列，，，，V,使得(%，v,(,》, (w.v.均属于E(G回，则称顶点，到，存在一条路轻(Pth) 2.有向阳的路径 在有向图G中。路径也是有向的.它由E(G)中的有向边,《w:Va>,, we,v>组成。 3,略径长度 路径长度定义为该路径上边的数目， 4.简单路径 4
4 五、子图 设 G=(V，E)是一个图，若 V'是 V 的子集，E'是 E 的子集，且 E'中的边所关联的顶点 均在 V'中，则 G'=(V'，E')也是一个图，并称其为 G 的子图(Subgraph)。 【例】下图给出了有向图 Gl 的若干子图；图 7.3 给出了无向图 G2 的若干个子图。 注意： 设 V'={v1，v2，v3}，E'={(vl，v2)，(v2，v4)}，显然，V'属于 V(G2)，E'属于 E(G2)，但 因为 E'中序偶对(v2，v4)所关联的顶点 v4 不在 V'中，所以(V'，E')不是图，也就不可能是 G2 的子图。 六、路径(Path) 1．无向图的路径 在无向图 G 中，若存在一个顶点序列 vp,vi1，vi2,…，vim，vq，使得(vp，vi1)，(vi1，vi2)，…， (vim，vq)均属于 E(G)，则称顶点 vp 到 vq 存在一条路径(Path)。 2．有向图的路径 在有向图 G 中，路径也是有向的,它由 E(G)中的有向边，，…， 组成。 3．路径长度 路径长度定义为该路径上边的数目。 4．简单路径
若一条路径上除了V,和”，可以相同外，其余顶点均不相同，则称此路径为一条简单路 径。 【例】在图G中项点序列，：，V,是一条从项点v到顶点，的长度为3的简单路轻 【例】在图中，顶点序列，，，，V是一条从项点m到原点的长度为4的路径， 但不是商单路径 5.简单目席或简单环(Cyc1o) 起点和终点相同(w,=v,)的简单路径称为简单国路或简单环(Cyc1®)。 【例】图G中，项点序列，，，是一个长度为3的简单环 【例】有白图G中，顶点序列，，是一长度为2的有向简单环. 6,有根图和图的根 在一个有向图中，若存在一个顶点，从该暖点有路径可以到达图中其它所有顶点，则 称此有向图为有根图。V称作图的根。 七、连通图和连通分量 1,顶点间的连通性 在无向图G中，若从顶点：到顶点有路径（当然从到”也一定有路径），则称，和 V,是连通的， 2,连通图 若YG)中任意两个不月的项点”和V都连通（即有路径），则称G为连通图 (Con-nected Graph). 【例】图G,和G是连通图. 0 3 (h)Ge (e)Ga 3.违通分量 无向图G的极大连通子图称为G的连通分量(Comnected Component)。 注意： 任何连通图的连通分量只有一个，即是其自身 ②幸连通的无向图有多个连通分量。 八、强连通图和强连通分量 1,强连通图 有向图G中，若对于V(G)中任意两个不同的顶点和￥，都存在从到，以及从 到，的路径，则称G是强连通图。 5
5 若一条路径上除了 vp 和 vq 可以相同外，其余顶点均不相同，则称此路径为一条简单路 径。 【例】在图 G2 中顶点序列 vl，v2，v3，v4 是一条从顶点 v1到顶点 v4的长度为 3 的简单路径 【例】在图 G2 中，顶点序列 v1，v2，v4，v1，v3 是一条从顶点 v1 到顶点 v3 的长度为 4 的路径， 但不是简单路径； 5．简单回路或简单环(Cycle) 起点和终点相同(vp=vq)的简单路径称为简单回路或简单环(Cycle)。 【例】图 G2 中，顶点序列 v1，v2，v4，v1 是一个长度为 3 的简单环 【例】有向图 G1 中，顶点序列 v1，v2，v1 是一长度为 2 的有向简单环。 6．有根图和图的根 在一个有向图中，若存在一个顶点 v，从该顶点有路径可以到达图中其它所有顶点，则 称此有向图为有根图，v 称作图的根。 七、连通图和连通分量 1．顶点间的连通性 在无向图 G 中，若从顶点 vi 到顶点 vj 有路径(当然从 vj 到 vi 也一定有路径)，则称 vi 和 vj 是连通的。 2．连通图 若 V(G)中任意两个不同的顶点 vi 和 vj 都连通(即有路径)，则称 G 为连通图 (Con-nected Graph)。 【例】图 G2，和 G3 是连通图。 3．连通分量 无向图 G 的极大连通子图称为 G 的连通分量(Connected Component)。 注意： ① 任何连通图的连通分量只有一个，即是其自身 ② 非连通的无向图有多个连通分量。 八、强连通图和强连通分量 1．强连通图 有向图 G 中，若对于 V(G)中任意两个不同的顶点 vi和 vj，都存在从 vi到 vj 以及从 vj 到 vi 的路径，则称 G 是强连通图
2.强连通分量 有向图的极大强连通子图称为G的强连通分量， 注意： ①强连通图只有一个强连通分量，即是其白身。 ②幸强违通的有向图有多个强连分量。 【例】下哥中的G,不是强连通图。因为气到V,没有路径，但它有两个强连通分量，如右图 所示。 OY V3 的内个强适通分量 (a)GI 九、网络 若将图的每条边赋上一个权，则称这种蒂权图为网络Network). 注意： 权是表示两个顶点之闻的距离、耗贵等具有某种意义的数。 【例】下图就是一个网格的例子。 3 Va 10 Va 网络不制 十、练习题 单项选择题 1,在一个图G中，所有项点的度数之和等于所有边数之和的()倍。 A,1/2 B.1 C.2 D.4 2.一个具有。个顶点的无向完全图包含( )条边。 A.n(n-l)B.n(+l） C.n(n-1)/2D.n(m+1)/2 3,一个具有■个项点的有向完全图包含( )条边。 A.■(n-1) B.n(n+1) C.m(n-1)/2D.n(m+1)/2 4.对干具有■个项点的图。若采用邻接矩阵表示，则该矩阵的大小为()
6 2．强连通分量 有向图的极大强连通子图称为 G 的强连通分量。 注意： ① 强连通图只有一个强连通分量，即是其自身。 ② 非强连通的有向图有多个强连分量。 【例】下图中的 G1 不是强连通图，因为 v3 到 v2 没有路径，但它有两个强连通分量，如右图 所示。 九、网络 若将图的每条边都赋上一个权，则称这种带权图为网络(Network)。 注意： 权是表示两个顶点之间的距离、耗费等具有某种意义的数。 【例】下图就是一个网络的例子。 十、练习题 单项选择题 1．在一个图 G 中，所有顶点的度数之和等于所有边数之和的（ ）倍。 A．1/2 B．1 C．2 D．4 2．一个具有 n 个顶点的无向完全图包含（ ）条边。 A．n（n−1） B．n（n+1） C． n（n−1）/2 D． n（n+1）/2 3．一个具有 n 个顶点的有向完全图包含（ ）条边。 A．n（n−1） B．n（n+1） C． n（n−1）/2 D． n（n+1）/2 4．对于具有 n 个顶点的图，若采用邻接矩阵表示，则该矩阵的大小为（ ）
A,日 B.n' C.n-1 D.(n-1)· 5.对于一个具有n个项点和©条边的无向图。若采用邻接表表示，则所有项点邻接表 中的结点总数为( A,■ B.e C.2n D.2e 6.在有白图的邻接表中，每个顶点忽接表链接着该顶点所有〔)邻接点。 A,入边 B。出边 C.入边和出边 D. 不是入边也不是出边 7,在有向图的道邻接表中，每个顶点邻接表链接着该顶点所有《)忽接点。 A,入边 B.出边 C,入边和出边 D。不是入边他不是出边 8.邻接表是图的一种( A,顺序存储结构 B。链式存储结构 C,素引存储结构 D.数列存储结构 9。如果从无向图的任一项点出发进行一次深度优先搜索即可访月所有项点，测该图一 定是( A.完全图 B.连通图 C.有目路 D.一棵树 10.下列有关图遍历的说法不正确的是( A。连通图的深度优先搜素是一个递归过程 B。图的广度优先被索中邻接点的寻找具有“先进先出”的特狂 C,非连通图不隆用深度优先授素法 D.图的遍历要求每一顶点仅被防问一次 11。无向图的忽接矩阵是一个()· A,对移矩阵 B.零矩库 C,上三角矩库 D,对角矩降 12.图的深度优先着历算法类似于二叉树的(》追历。 A,先序 B.中序C.后序D.层浅 13.图的广度优先游历算法类似于二叉树的()治历。 A先序 B.中序 C.后序D.层次 14。己知下图所示的一个图，若从项点V,出发，按深度优先瘦素法进行遍历。则可能 得到的一种顾点序列为《)。 A.V.VV.V.YaVaV.V: B.ViYaV.VV.VaV.V C.ViVeVV,VV,VV: D.ViVYV:VV.ViV. V: 7
7 A．n B．n 2 C．n−1 D．（n−1） 2 5．对于一个具有 n 个顶点和 e 条边的无向图，若采用邻接表表示，则所有顶点邻接表 中的结点总数为（ ）。 A．n B．e C．2n D．2e 6．在有向图的邻接表中，每个顶点邻接表链接着该顶点所有（ ）邻接点。 A．入边 B． 出边 C．入边和出边 D． 不是入边也不是出边 7．在有向图的逆邻接表中，每个顶点邻接表链接着该顶点所有（ ）邻接点。 A．入边 B．出边 C．入边和出边 D．不是入边也不是出边 8．邻接表是图的一种（ ）。 A．顺序存储结构 B．链式存储结构 C．索引存储结构 D．散列存储结构 9．如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一 定是（ ）。 A．完全图 B．连通图 C．有回路 D．一棵树 10．下列有关图遍历的说法不正确的是（ ）。 A．连通图的深度优先搜索是一个递归过程 B．图的广度优先搜索中邻接点的寻找具有“先进先出”的特征 C．非连通图不能用深度优先搜索法 D．图的遍历要求每一顶点仅被访问一次 11．无向图的邻接矩阵是一个（ ）。 A．对称矩阵 B． 零矩阵 C．上三角矩阵 D．对角矩阵 12．图的深度优先遍历算法类似于二叉树的（ ）遍历。 A．先序 B． 中序 C．后序 D．层次 13．图的广度优先遍历算法类似于二叉树的（ ）遍历。 A．先序 B． 中序 C．后序 D．层次 14．已知下图所示的一个图，若从顶点 V1 出发，按深度优先搜索法进行遍历，则可能 得到的一种顶点序列为（ ）。 A．V1V2V4V8V3V5V6V7 B．V1V2V4V5V8V3V6V7 C．V1V2V4V8V5V3V6V7 D．V1V3V6V7V2V4V5V8 V6 V7 V1 V2 V3 V8 V4 V5
15.已知如图1所不的一个图，若从顶点ā出发，按广度优先搜索法进行游历，则可能 得到的一种顶点序列为《)。 A.abcedf B.abcefd C.aebefd D.acfdeb 图1 16。己知如图1所示的一个图，若从顶点。出发，按深度优先搜索法进行遍历。则可能 得到的一种顶点序列为()。 A.abecdf B.acfebd C.aebefd D.aedfcb 然习思答案 单项选择题 1.C2.C3.A4.B5,D6.B7.A8.B9.B 10.C11.A12.A13.D14.C15.B16.D 8
8 15．已知如图 1 所示的一个图，若从顶点 a 出发，按广度优先搜索法进行遍历，则可能 得到的一种顶点序列为（ ）。 A．abcedf B．abcefd C．aebcfd D．acfdeb 图 1 16．已知如图 1 所示的一个图，若从顶点 a 出发，按深度优先搜索法进行遍历，则可能 得到的一种顶点序列为（ ）。 A．abecdf B．acfebd C．aebcfd D．aedfcb 练习题答案 单项选择题 1．C 2．C 3．A 4．B 5．D 6．B 7．A 8. B 9. B 10. C 11. A 12．A 13．D 14．C 15．B 16．D b d f e c a b d f e c a