数据结构(本)课程辅导与练习-第7章

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表示一条有向边，vi是边的始点(起点)，vj是边的终点。因此，vi，vj和vj，vi是两条不同的有向边。（2）有向图的表示【例】下面(a)图中G1是一个有向图。图中边的方向是用从始点指向终点的箭头表示的，该图的顶点集和边集分别为：V(G1)={v1，v2，v3}E(G1)={v1，v2，v2，v1，v2，v3}22．无向图若图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)或vl，v2是E(G)中的一条边，则要求v1≠v2。此外，不允许一条边在图中重复出现，即只讨论简单的图。3．图G的顶点数n和边数e的关系（1）若G是无向图，则0≤e≤n(n-1)/2恰有n(n-1)/2条边的无向图称无向完全图(Undireet-edCompleteGraph)（2）若G是有向图，则0≤e≤n(n-1)恰有n(n-1)条边的有向图称为有向完全图(DirectedCompleteGraph)。注意：完全图具有最多的边数。任意一对顶点间均有边相连。【例】上面(b)图的G2就是具有4个顶点的无向完全图。四、图的边和顶点的关系31.无向边和顶点关系若(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关联于vi和vj或称vi，vj与顶点vi和vj相关联【例】在下图G1中，关联于顶点v2的弧是v1，v2，v2，v1和v2，v3。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和度数之间有如下关系：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)中的有向边vp，vi1，vi1，vi2，…，vim，vq组成。3．路径长度路径长度定义为该路径上边的数目。4．简单路径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-nectedGraph)。【例】图G2，和G3是连通图。3．连通分量无向图G的极大连通子图称为G的连通分量(ConnectedComponent)。注意：①任何连通图的连通分量只有一个，即是其自身②非连通的无向图有多个连通分量。八、强连通图和强连通分量1．强连通图有向图G中，若对于V(G)中任意两个不同的顶点vi和vj，都存在从vi到vj以及从vj到vi的路径，则称G是强连通图。62．强连通分量有向图的极大强连通子图称为G的强连通分量。注意：①强连通图只有一个强连通分量，即是其自身。②非强连通的有向图有多个强连分量。【例】下图中的G1不是强连通图，因为v3到v2没有路径，但它有两个强连通分量，如右图所示。九、网络若将图的每条边都赋上一个权，则称这种带权图为网络(Network)。注意：权是表示两个顶点之间的距离、耗费等具有某种意义的数。【例】下图就是一个网络的例子。十、练习题单项选择题1．在一个图G中，所有顶点的度数之和等于所有边数之和的（）倍。A．1/2B．1C．2D．42．一个具有n个顶点的无向完全图包含（）条边。A．n（n1）B．n（n1）C．n（n1）/2D．n（n1）/23．一个具有n个顶点的有向完全图包含（）条边。A．n（n1）B．n（n1）C．n（n1）/2D．n（n1）/24．对于具有n个顶点的图，若采用邻接矩阵表示，则该矩阵的大小为（）。7A．nB．n2C．n1D．（n1）25．对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则所有顶点邻接表中的结点总数为（）。A．nB．eC．2nD．2e6．在有向图的邻接表中，每个顶点邻接表链接着该顶点所有（）邻接点。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．V1V2V4V8V3V5V6V7B．V1V2V4V5V8V3V6V7C．V1V2V4V8V5V3V6V7D．V1V3V6V7V2V4V5V8V6V7V1V2V3V8V4V5815．已知如图1所示的一个图，若从顶点a出发，按广度优先搜索法进行遍历，则可能得到的一种顶点序列为（）。A．abcedfB．abcefdC．aebcfdD．acfdeb图116．已知如图1所示的一个图，若从顶点a出发，按深度优先搜索法进行遍历，则可能得到的一种顶点序列为（）。A．abecdfB．acfebdC．aebcfdD．aedfcb练习题答案单项选择题1．C2．C3．A4．B5．D6．B7．A8.B9.B10.C11.A12．A13．D14．C15．B16．Dbdfecabdfeca