数据结构答案第8章图学习指导

《数据结构答案第8章图学习指导》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、8.1知识点分析1.图的定义图(Graph)是由非空的顶点(Vertices)集合和一个描述顶点Zl'可关系边(Edges)的有限集合组成的一种数据结构。可以用二元组定义为：G=(V,E)其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合。2.图的相关术语(1)无向图在一个图中，如果每条边都没有方向，则称该图为无向图。(2)冇向图在一个图中，如果每条边都冇方向，则称该图为冇向图。(3)无向完全图在一个无向图小，如果任意两顶点都有一条直接边相连接，则称该图为无向完全图。在一个含有n个顶点的无向完全图中，有

2、n(n-l)/2条边。(4)有向完全图在一个冇向图中，如果任意两顶点Z间都冇方向互为相反的两条弧相连接，则称该图为有向完全图。在一个含有n个顶点的有向完全图屮，有n(n・l)条弧。(5)顶点的度在无向图屮，一个顶点拥有的边数，称为该顶点的度。记为TD(v)o在有向图屮，一个顶点拥有的弧头的数目，称为该顶点的入度，记为ID(v)；—个顶点拥冇的弧尾的数目，称为该顶点的出度，记为OD(v)；—个顶点度等于顶点的入度+出度，B

3、J：TD(v)=ID(v)+OD(v)o(6)权图的边或弧有时具有与它有关的数据信息，这个数

4、据信息就称为权(Weight)。(7)网边(或弧)上带权的图称为网(Network)o(8)路径、路径长度顶点W到顶点Vj之间的路径(Path)是指顶点序列Vi,Vi],vi2,vim,Vj.o其中，(％%),(Vi],vi2)，...,(Vim,.Vj)分别为图中的边。路径上边的数目称为路径长度。(9)回路、简单路径在一条路径中，如果其起始点和终止点是同一顶点，则称其为回路或者环(Cycle)o如果一条路径上所有顶点除起始点和终止点外彼此都是不同的，则称该路径为简单路径。(10)子图对于图G=(V,E),G，=

5、(VE9,若存在V，是V的子集，E，是E的子集，则称图G，是G的一个了图。(1)连通图、连通分量在无向图中，如果从一个顶点V.到另一个顶点Vj(明)有路径，则称顶点V.和Vj是连通的。任意两顶点都是连通的图称为连通图。无向图的极大连通了图称为连通分量。(2)强连通图、强连通分量对于有向图來说，若图中任意对顶点vi和vj(i力)均有从-个顶点vi到另一个顶点vj有路径，也有从Vj到申的路径，则称该有向图是强连通图。有向图的极人强连通子图称为强连通分量(3)生成树连通图G的一个子图如果是一棵包含G的所有顶点的树，贝

6、IJ该子图称为G的生成树(SpanningTree)o1.图的存储表示(1)邻接矩阵邻接矩阵是表示顶点之间相邻关系的矩阵。(2)邻接表邻接表是图的一种顺序存储与链式存储结合的存储方法。2.图的遍历图的遍历是指从图的某一顶点出发，对图屮的所有顶点访问，且仅访问一次的方法。常用的冇深度优先搜索和广度优先搜索两种方法。3.最小生成树连通图的一次遍历所经过的边的集合及图中所有顶点的集合就构成了该图的一棵生成树，对连通图的不同遍历，就可能得到不同的牛:成树，牛成树中权值之和为最小的牛:成树，称为最小生成树。4.最短路径在网

7、中，两个顶点Z间所有路径中，边的权值Z和最知的那一条路径。这条路径就称为两点之间的最短路径。8.2典型习题分析【例1】设有两个无向图6=(V,E),G=(V,E),如果G，是G生成了树，则下述叙述不正确的是()oA.G，是G的子图B.G，是G的连通分量C.G'是G的无环了图D.G'是G极小连通了图，H.V—V分析：如果G是G生成子树，显然G是G的子图、G，是G的无环子图、G，是G的连通分量和CT是G极小连通子图但是V学V,故D不正确，答案为D。【例2】若一个冇向图具冇拓扑序列，则它的短阵必为()。A.对称矩阵B.

8、三角矩阵C.一般矩阵D.B或C分析：拓扑排序存在当仅当有向无环图，若一个有向图的邻接矩阵是三角形矩阵，则该图一定无环；但一个无环图的有向图的邻接矩阵未必是三饬形。因此，应该选择D。【例3】川邻接矩阵表示图时，若图1000个顶点，1000条边，贝U形成的邻接矩阵有多少矩阵元素？有多少非零元素？是否稀疏矩阵？解：一个图中有1000个顶点，其邻接矩阵中的矩阵元素有100（）2=1000000个。它有］000个非零元素（对于冇向图）或2000个非零元素（对于无向图），因此是稀疏矩阵。【例4】用邻接矩阵表示图时，矩阵元索的

9、个数与顶点个数是否相关？与边的条数是否相关？答：用邻接矩阵表示图，矩阵元索的个数是顶点个数的平方，与边的条数无关。矩阵中非零元素的个数与边的条数有关。【例5】Prim算法最小生成树的时间复杂度为,因此它适合于图;Kruskal算法最小生成树的时间复杂度为,因此适合于图，且图应该用作为存储结构。分析：因为Prim算法的时间复杂度只与顶点数n有关，故对稀疏图不太适合，而Kru