简单的数据结构(4)

起点和终点相同(vp=vq)的简单路径称为简单回路或简单环(cycle).例如图G2中，顶点序列vl，v2，v4，v1是一个长度为3的简单环.例如图4-4-1中有向图Gl中，顶点序列vl，v2，vl是一长度为2的有向简单环. 6.有根图和图的根

在一个有向图中，若存在一个顶点v，从该顶点有路径可以到达图中其它所有顶点，则称此有向图为有根图，v称作图的根. (五)连通图和连通分量 1.顶定间的连通性

在无向图G中，若从顶点vi到顶点vj有路径(当然从Vj到Vi也一定有路径)，则称vi和vj是连通的. 2.连通图

若V(G)中任意两个不同的顶点vi和vj都连通(即有路径)，则称G为连通图(Con-nected Graph).例如图4-4-1中G2和G3是连通图. 3.连通分量

无向图G的极大连通子图称为G的连通分量(connected Component).注意：任何连通图分量只有一个，即是其自身；另外非连通的无向图有多个连通分量.例如图4-4-3中的G4是非连通图.它有两个连通分量Hl和H2.

图4_4—3具有两个分量的非连通图G4

(六)强连通图和强连通分量 1.强连通图

有向图G中，若对于V(G)中任意两个不同的顶点vi和vj，都存在从vi到vj以及从vj到vi的路径，则称G是强连通图. 2.强连通分量

有向图的极大强连通子图称为G的强连通分量.强连通图只有一个强连通分量，即是其自身.非强连通的有向图有多个强连通分量.例如图4-4-4中的G1不是强连通图，因为v3到v2没有路径，但它有两个强连通分量，如图4-4-5所示.

16

(六)图的存储结构

图的存储方法有很多，我们这里只介绍图的邻接矩阵表示法.在图的邻接矩阵表示法中：

①用邻接矩阵表示顶点间的相邻关系； ②用一个顺序表来存储顶点信息.

设G：(V，E)是具有n个顶点的图，则G的邻接矩阵是具有如下性质的n阶方阵，其规模为n ×n：

例如图4-4-6中无向图G5和有向图G6的邻接矩阵分别为A1和A2. 例58 G是一个非连通无向图，共有28条边，则该图至少有____个顶点. 8个顶点的完全图共有28条边，再加一个孤立顶点使G成为非连通的.其他情况，由于点未充分利用必定多于9个.所以答案是9.

(七)图的遍历

给出一个图G和其中任意一个结点V0，从V0出发系统地访问G中所有结点，每一个结点被访问一次，这就叫图的遍历.遍历图的结果是按访问顺序将结点排成一个线性序列.通常有两种遍历方法：深度优先搜索和广度优先搜索，他们对

17

无向图和有向图都适用. 1.深度优先搜索

深度优先搜索类似于树的前序遍历，是树的前序遍历的推广.假设初始时所有结点未曾被访问，深度优先搜索从某个结点V0出发，然后依次访问从V0的未被访问的邻接点出发深度优先搜索遍历图，直至图中所有和V0有路径相连的结点都被访问到.若此时图中尚有结点未被访问，则以另选一个未曾访问的结点为起始点，重复上述过程，直至图中所有结点都被访问为止.换句话说，深度优先搜索遍历图的过程是以V0为起始点，由左而右，依次访问由V0出发的每条路径.例如，上图G6，从V2出发，按深度优先搜索得到的序列是：V2一V1一V0一V4一V3.

2.广度优先搜索

广度优先搜索类似于树的按层次遍历的过程.假设从图中某结点V0出发，在访问了V0之后依次访问V0的各个未曾访问的邻接点，然后分别从这些邻接点出发按广度优先搜索的顺序遍历图，直至图中所有可被访问的结点都被访问到.若此时图中尚有结点未被访问，则以另选一个未曾访问的结点为起始点，重复上述过程，直至图中所有结点都被访问为止.换句话说，广度优先搜索遍历图的过程是以V0为起始点，由近及远，依次访问和V0有路径相连且路径长度为1，2，3，?的结点.例如，图4-4-6中G6，从V2出发，按广度优先搜索得到的序列是：V2—V1—V3—V0—V4

例59如图有向图，试给出(1)邻接矩阵(2)强连通分量(3)从①出发的深度优先遍历序列(4)从⑥出发的广度优先遍历序列. （1）邻接距阵

(2)强连通分量：在有向图G中，如果对于每一对Vi，Vj∈V(顶点集)，且vi≠vj， 从vi道vj和从vj的vi都存在路径，则称G是强连通图.有向图中的极大强连通子图称作有向图的强连通分量.由此得到强连通分量如图所示.

(3)从①出发的深度优先遍历序列可以为：①④②③⑤⑥.

(4)从⑥出发的广度优先遍历序列可以为：⑥②⑤①③④.(注意(3)(4)答案不惟一) 【练习题】 一、选择题

1.如图说示，在下面的5个序列中符合深度优先遍历的序列有_______

18

(1)aebdfc (2)acfdeb (3)aedfcb (4)aefdcb (5)aefdbc A.5个 B.4个 C.3个 D.2个

2.设无向图的顶点个数为n，则该无向图最多有______条边. A.n-1 B.n(n—1)/2 C.n(n+1)/2 D.0 E.n2

3.一个图中包含有k个连通分量，若按深度优先(DFS)搜索方法访问所有结点，则必须调用_____次深度优先遍历算法. A.k B.1 C.k-1 D.k+l

4.具有n个顶点的有向图最多有____条边. A.n B.n(n-1) C.n(n+1) D.n2

5.一个n个顶点的连通无向图，其边的个数至少为_____. A.n-1 B.n C.n+l D.nlog2n

6.在一个具有n个顶点的有向图中，若所有顶点的出度之和为s，则所有顶点的人度之和为_______ A.s B.s-l

C.s+1 D.n

7.在一个无向图中，若两个顶点之间的路径长度为k，则该路径上的顶点数为______ A.k B.k+1 C.k+2 D.2k

8.一个有n个顶点的无向连通图，它说包含的连通分量个数为______ A.0 B.1 C.n D.n+l 二、问题求解

1.无向图G有16条边，有3个4度顶点、4个3度顶点，其余顶点的度均小于3，则G至少_____个顶点.

19

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库简单的数据结构(4)在线全文阅读。