武汉软件工程职业学院《数据结构义》图.doc

1．掌握图的定义及基本术语。 2. 掌握图的存储结构（包括邻接矩阵和邻接表），以及这些存储表示上的典型操作。 教学重点： 图的定义及其基本概念（包括图的定义，图的连通性，图的路径和路径长度，图中各顶点的度，有向图和无向图的概念，完全图，子图的概念。无向连通图的强连通分量，有向强连通图的强连通分量等 2、图的存储结构。 教学难点： 图的存储结构 授课内容 第5章 图 图(Graph)是一种较线性表和树更为复杂的数据结构。在线性表中，数据元素之间仅有线性关系，每个数据元素只有一个直接前驱和一个直接后继；在树形结构中，数据元素之间有着明显的层次关系，并且每一层上的数据元素可能和下一层中多个元素(即其孩子结点)相关，但只能和上一层中一个元素(即其双亲结点)相关；而在图形结构中，结点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。由此，图的应用极为广泛，特别是近年来的迅速发展，已渗入到诸如语言学、逻辑学、物理、化学、电讯工程、计算机科学以及数学的其它分支中。 5.1 图的基本概念 在图中的数据元素通常称做顶点(Vertex)，V是顶点的有穷非空集合；E是用顶点对 表示的边（Edge）的有穷集合。 若 vi,vj ∈VR必有 vi,vj ∈VR，即E是对称的，则以无序对(vi,vj)代替这两个有序对，表示vi和vj之间的一条边（Edge)，此时的图称为无向图(Undigraph)。????若vi,vj∈E，则 vi,vj 表示从vi 到vj的一条弧(Arc)，且称v为弧尾(Tail)或初始点(Initial node)，称vj为弧头(Head)或终端点(Terminal node)，此时的图称为有向图(Digraph)。 [例如] 图5-1-1给出两个图G1和G2，其中G1是无向图，G2是有向图。在有向图中用箭头表示弧的方向，箭头从弧尾指向弧头。 图G1 图G2 图5-1-1 有向图与无向图 在上面两个图结构中，一个是有向图，即每条边都有方向，另一个是无向图，即每条边都没有方向。 [例如] 图5-1-2(a)中G3是有向图，定义此图的谓词P(vi，vj )则表示从vi到vj的一条单向通路。????G1=(V1,{A1})其中：????V1={v1,v2,v3,v4}????A1={v1,v2,v1,v3,v3,v4,v4,v1}图5-1-2 (b)中G4为无向图????G2=(V2,{A2})其中：????V2={v1,v2,v3,v4,v5}????A2={(v1,v2),(v1,v4),(v2,v3) ,(v2,v5),(v3,v4),(v3,v5)} （a)有向图G3 ????(b)无向图G2图5-1-2图的示例 5.1.2 图的基本术语 在下面的讨论中，不考虑顶点到其自身的边或弧在图中重复出现，同时可以用n表示图中顶点的数目，用e表示边或弧的数目。 邻接点、相关边 对于无向图G=（V，E），若边（vi，vj）∈E，则称vi和vj互为邻接点（Adjacent），即vi和vj相邻接，而边（vi， vj ）则是与顶点vi和vj相关联的边。 对于有向图G=（V，A），若弧（vi，vj）∈E，则称为顶点vi邻接到顶点vj，顶点vj邻接自顶点vi，而弧（vi， vj ）和顶点vi、 vj相关联。 完全图：在一个有n个顶点的无向图中，若每个顶点到其它（n-1）个顶点都连有一 条边，则图中共有n(n-1)/2条边，这种图称为完全图（Complete graph，也称完备图）。 ??? ? 左图所示就是n=4的完全图，它一共有六条边。 子图：设有两个图G =(V,E)和G’=(V’,E’)，若V(G’)是V(G)的子集，且E(G’) 是E(G)的子集，则称G’是G的子图(Subgraph)。 [例如] 图5-1-3所示的图是图5-1-1中G1的一些子图。 图5-1-3 子图 [例如] 图5-1-4是子图的一些例子。 图5-1-4 顶点的度：图中与每个顶点相连的边数，叫该顶点的度(Degree)。例如图5-1-2的 图G1中，顶点①的度数为2，顶点②的度数为3，……。对于有向图，顶点的度分为入度和出度，入度是以该顶点为终点的入边数目；出度是以该顶点为起点的出边数目，该顶点的度等于其入度和出度之和。例如在图5-1-1的图G2中，顶点①的入度为1，出度为2，而顶点②的入度为1，出度为0，因为有一条边指