数据结构答案 第8讲 图学习指导.docVIP

第8章 图 8.1 知识点分析 1．图的定义 图（Graph）是由非空的顶点（Vertices）集合和一个描述顶点之间关系——边（Edges）的有限集合组成的一种数据结构。可以用二元组定义为： G＝（V，E） 其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合。 2．图的相关术语 （1）无向图在一个图中，如果每条边都没有方向，则称该图为无向图。 （2）有向图在一个图中，如果每条边都有方向，则称该图为有向图。 （3）无向完全图在一个无向图中，如果任意两顶点都有一条直接边相连接，则称该图为无向完全图。在一个含有n个顶点的无向完全图中，有n(n-1)/2条边。 （4）有向完全图在一个有向图中，如果任意两顶点之间都有方向互为相反的两条弧相连接，则称该图为有向完全图。在一个含有n个顶点的有向完全图中，有n (n-1) 条弧。 （5）顶点的度在无向图中一个顶点拥有的边数，称为该顶点的度。记为TD(v)。 在有向图中，一个顶点拥有的弧头的数目，称为该顶点的入度，记为ID(v)；一个顶点拥有的弧尾的数目，称为该顶点的出度，记为OD(v)；一个顶点度等于顶点的入度+出度，即：TD(v)=ID(v)＋OD(v)。 （6）权图的边或弧有时具有与它有关的数据信息，这个数据信息就称为权（Weight）。 （7）网边（或弧）上带权的图称为网（Network）。 （8）路径、路径长度顶点vi到顶点vj之间的路径（Path）是指顶点序列vi,vi1,vi2, …, vim,vj.。其中，（vi,vi1），(vi1,vi2)，…,(vim,.vj)分别为图中的边。路径上边的数目称为路径长度。 （9）回路、简单路径在一条路径中，如果其起始点和终止点是同一顶点，则称其为回路或者环（Cycle）。如果一条路径上所有顶点除起始点和终止点外彼此都是不同的，则称该路径为简单路径。 (10）子图对于图G=（V，E），G’=（V’，E’），若存在V’是V的子集 ，E’是E的子集 ，则称图G’是G的一个子图。 （11）连通图、连通分量在无向图中，如果从一个顶点vi到另一个顶点vj(i≠j)有路径，则称顶点vi和vj是连通的。任意两顶点都是连通的图称为连通图。无向图的极大连通子图称为连通分量。 （12）强连通图、强连通分量对于有向图来说，若图中任意一对顶点vi 和vj(i≠j)均有从一个顶点vi到另一个顶点vj有路径，也有从vj到vi的路径，则称该有向图是强连通图。有向图的极大强连通子图称为强连通分量 （13）生成树连通图G的一个子图如果是一棵包含G的所有顶点的树，则该子图称为G的生成树（Spanning Tree）。 3．图的存储表示 （1）邻接矩阵邻接矩阵是表示顶点之间相邻关系的矩阵。 （2）邻接表邻接表是图的一种顺序存储与链式存储结合的存储方法。 4．图的遍历图的遍历深度优先有哪些信誉好的足球投注网站广度优先有哪些信誉好的足球投注网站。 5．最小生成树 连通图的一次遍历所经过的边的集合及图中所有顶点的集合就构成了该图的一棵生成树，对连通图的不同遍历，就可能得到不同的生成树，生成树中权值之和为最小的生成树，称为最小生成树。 6．最短路径 在网中，两个顶点之间所有路径中，边的权值之和最短的那一条路径。这条路径就称为两点之间的最短路径。 8.2 典型习题分析 【例1】设有两个无向图G＝（V，E），G＝（V′，E′），如果G′是G生成子树，则下述叙述不正确的是（　）。 A．G′是G的子图　　　　　　　B．G′是G的连通分量 C．G′是G的无环子图　　　　　D．G′是G极小连通子图，且V′＝V 分析：如果G′是G生成子树，显然G是G的子图、G′是G的无环子图、G′是G的连通分量和G′是G极小连通子图但是V′≠V，故D不正确，答案为D。 【例2】若一个有向图具有拓扑序列，则它的矩阵必为。 A．对称矩阵 B．三角矩阵 C．一般矩阵 D．B或C 分析：拓扑排序存在当仅当有向无环图，若一个有向图的邻接矩阵是三角形矩阵，则该图一定无环；但一个无环图的有向图的邻接矩阵未必是三角形。因此，应该选择D。 【例3】用邻接矩阵表示图时，若图中有1000个顶点，1000条边，则形成的邻接矩阵有多少矩阵元素？有多少非零元素？是否稀疏矩阵？ 解：一个图中有1000个顶点，其邻接矩阵中的矩阵元素有10002 = 1000000个。它有1000个非零元素（对于有向图）或2000个非零元素（对于无向图），因此是稀疏矩阵。 【例4】用邻接矩阵表示图时，矩阵元素的个数与顶点个数是否相关？与边的条数是否相关？ 答：用邻接矩阵表示图，矩阵元素的个数是顶点个数的平方，与边的条数无关。矩阵中非零元素的个数与边的条数有关。 【例5】Prim算法最小生成树的时间复杂度为____，因此它适合于___________图；Kruskal算法