第7章图（Graph）.ppt

1、第7章 图（Graph）,图是一种比树更为复杂的非线性数据结构。 1.线性表: 数据元素之间仅有线性关系. (每个elem只有一个直接前驱和一个直接后继) 2.树形结构:elem之间有明显的层次关系. (每一层上的数据元素可能和下一层中多个元素相关,但只能和上一层中一个元素(双亲)相关) 3.图形结构:结点之间的关系可以是任意的. (图中任意两个数据元素之间都可能相关联 ) 图的应用十分广泛。最典型的应用领域有电路分析、寻找最短路线、项目规划、鉴别化合物、统计力学、遗传学、控制论、语言学，乃至社会科学。实际上，在所有的数据结构中，图的应用是最广泛的。,7.1.1 图的定义,1.图（Graph）

2、是由集合V和集合E组成， 记为: G=(V,E). 图中的数据元素V,称为顶点(Vertice，也叫作节点或点). V:是顶点的有穷非空集合. E:边的集合. （edge，两个顶点之间的关系,也叫作弧或连线） 在图7.1中，顶点v2 邻接于顶点v1 ，而v1 邻接至顶点v2 。边关联于顶点v1 而关联至顶点v2 。顶点v2 邻接至顶点v3 且邻接于顶点v3 。边是关联于顶点v2 而关联至顶点v3 。对于无向图来说，“至”和“于”的含义是相同的。,1.带方向的边叫有向边(directed edge)，简称为弧； 用顶点的有序对表示，和是不同的 . 2. 而不带方向的边叫无向边(undirecte

3、d edge)，简称为边。 用顶点的无序对表示，(vi ,vj)和(vj ,vi)表示同一条边。 表示从顶点vi到vj 的一段弧 Vi：称为边的始点或者弧尾 Vj：称为边的终点或者弧头,如果使用集合的表示方法，图7.1中的两个图可以用如下方法表示： 1. 图G1: G1=(V1，E1)； 其中顶点集 V1=v1，v2，v3，v4； 其中边集 E1=( v1，v2)，(v1，v3)，(v2，v3)，(v1，v4)， (v3，v4) 2. 图G2： G2=(V2，E2) 其中顶点集 V2= v1，v2，v3； 其中弧集 E2=， 如果图中所有的边都是无向边，那么该图叫做无向图(undirected

4、 graph)，图7.1中图G1就是无向图。 如果所有边都是有向的，那么该图叫做有向图(directed graph)， 图7.1中G2是一个有向图。,对图作一些限制： 第一，图中不能有从顶点自身到自身的边（即自身环），就是说不应有形如(vx，vx)的边或的弧。如图 (a)所示的带自身环的图不讨论。 第二，两个顶点vt和vu之间相关联的边不能多于一条。如图 (b)所示的多重图也不讨论。,(a)带自身环的图,（b）多重图,7.1.2图的术语 （1）完全图(complete graph)：在有n个顶点的无向图中，若有n(n-1)/2条边，则称此无向图为完全无向图，如图7.3 （a）所示的图G1。在

5、有n个顶点的有向图中，若有n(n-1)条边，则称此图为完全有向图，如图7.3(c)所示的图G3。 完全图中的顶点个数和边的个数都达到最大值。 （2）权(weight)：在某些图的应用中，边（弧）上具有与它相关的系数，称之为权。这些权可以表示从一个顶点到另一个顶点的距离、花费的代价、所需的时间和次数等。这种带权图也被称为网络(network)。,（3）邻接顶点(adjacent vertex)：在无向图G1中，若(u，v)是E(G)中的一条边，则称u和v互为邻接顶点，并称边(u，v)依附于顶点u和v。 （4）顶点的度：顶点的度是指依附于某顶点vi的边数, 通常记为TD(vi)。 在有向图中，要区

6、别顶点的入度和出度的概念。 所谓顶点vi的入度 过是指以vi为终点的弧的数目，记为ID(vi)； 所谓顶点vi的出度 过是指以vi为始点的弧的数目，记为OD(vi)。显然的： TD(vi)=ID(vi)+OD(vi),例如: 1. 在图7.1（G1）中顶点v1的度TD(v1)=3， 2. 在G2中顶点v2 的入度ID(v2)=2， 出度OD(v2 )=1， TD(v2 )=3。,可以证明，对于具有n个顶点、e条边的图，顶点vi的度TD(vi)与顶点的个数及边的数目满足关系： 2e= 例： 2*11+1 2*22+2,（5）路径与回路：路径上边的数目称为路径长度。 下图所示的无向图中，顶点v1到

7、顶点v5的路径有两条，分别为(v1，v2，v3，v5)与(v1，v4，v5)，路径长度分别为3和2。 如果路径的起点和终点相同(即vp=vq)，则称此路径为回路或环。序列中顶点不重复出现的路径称为简单路径， 上图所示的v1到v5的两条路径都为简单路径。除第一顶点与最后一个顶点之外，其它顶点不重复出现的回路为简单回路或者简单环。,（6）路径长度（path length）：对于不带权的图，路径长度是指路径上边的数目。对于带权图，路径长度是指路径上各边的权之和。 （7）简单路径与回路(cycle):对于一路径(v1, v2, vm)，若路径上各顶点均不相同，则称这条路径为简单路径。若路径上第一个顶点v1和最后一个顶点vm相同，则称这样的路径为回路或环。 （8）连通图与连通分量(connected graph and connected component)：若从顶点vi到顶点vj (ij)有路径，则vi和vj是连通的。,如果无向图中任意两个顶点vi和vj都是