第7章图（Graph）.ppt

第第7章章 图图（Graph）图是一种比树更为复杂的非线性数据结构。图是一种比树更为复杂的非线性数据结构。1.线性表线性表:数据元素之间仅有线性关系数据元素之间仅有线性关系.(每个每个elem只有一个直接前驱和一个直接后继只有一个直接前驱和一个直接后继)2.树形结构树形结构:elem之间有明显的层次关系之间有明显的层次关系.(每一层上的数据元素可能和下一层中多个元素相关每一层上的数据元素可能和下一层中多个元素相关,但只能和上一层中一个元素但只能和上一层中一个元素(双亲双亲)相关相关)3.图形结构图形结构:结点之间的关系可以是任意的结点之间的关系可以是任意的.(图中任意两个数据元素之间都可能相关联图中任意两个数据元素之间都可能相关联)图的应用十分广泛。图的应用十分广泛。最典型的应用领域有电路分析、最典型的应用领域有电路分析、寻找最短路线、项目规划、鉴别化合物、统计力学、遗寻找最短路线、项目规划、鉴别化合物、统计力学、遗传学、控制论、语言学，乃至社会科学。实际上，传学、控制论、语言学，乃至社会科学。实际上，在所在所有的数据结构中，图的应用是最广泛的。有的数据结构中，图的应用是最广泛的。7.1.1 图的定义 1.图（图（Graph）是由集合是由集合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.而不带方向的边叫无向边而不带方向的边叫无向边(undirected edge)，简称为边。简称为边。用顶点的无序对表示，用顶点的无序对表示，(vi,vj)和和(vj,vi)表示同一条边。表示同一条边。表示从顶点表示从顶点vi到到vj 的一段弧的一段弧 Vi：称为边的始点或者弧尾称为边的始点或者弧尾 Vj：称为边的终点或者弧头称为边的终点或者弧头vjvi如果使用集合的表示方法，图如果使用集合的表示方法，图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 graph)，图图7.1中图中图G1就是就是无向图无向图。如果所有边都是有向的，那么该图叫做有向图如果所有边都是有向的，那么该图叫做有向图(directed graph)，图图7.1中中G2是一个是一个有向图有向图。对图作一些限制：对图作一些限制：第一，图中不能有从顶点自身到自身的边（即自第一，图中不能有从顶点自身到自身的边（即自身环），就是说不应有形如身环），就是说不应有形如(vx，vx)的边或的边或的弧。如图的弧。如图(a)所示的带自身环的图不讨论。所示的带自身环的图不讨论。第二，两个顶点第二，两个顶点vt和和vu之间相关联的边不能多于之间相关联的边不能多于一条。如图一条。如图(b)所示的多重图也不讨论。所示的多重图也不讨论。1020123(a)带自身环的图（b）多重图 7.1.2图的术语图的术语（1）完全图）完全图(complete graph)：在有在有n个顶点的无向图中，个顶点的无向图中，若有若有n(n-1)/2条边，则称此无向图为条边，则称此无向图为完全无向图完全无向图，如图，如图7.3（a）所示的图所示的图G1。在有在有n个顶点的有向图中，若有个顶点的有向图中，若有n(n-1)条边，条边，则称此图为则称此图为完全有向图完全有向图，如图，如图7.3(c)所示的图所示的图G3。完全图中的顶点个数和边的个数都达到最大值。完全图中的顶点个数和边的个数都达到最大值。（2）权权(weight)：在某些图的应用中，边（弧）上具有与它相在某些图的应用中，边（弧）上具有与它相关的系数，称之为权。这些权可以表示从一个顶点到另一个关的系数，称之为权。这些权可以表示从一个顶点到另一个顶点的距离、花费的代价、所需的时间和次数等。这种带权顶点的距离、花费的代价、所需的时间和次数等。这种带权图也被称为网络图也被称为网络(network)。1234123（3）邻接顶点邻接顶点(adjacent vertex)：在无向图在无向图G1中，若中，若(u，v)是是E(G)中的一条边，则称中的一条边，则称u和和v互互为邻接顶点，并称边为邻接顶点，并称边(u，v)依附于顶点依附于顶点u和和v。（4）顶点的度：顶点的度：顶点的度是指依附于某顶点顶点的度是指依附于某顶点vi的边数的边数,通常记为通常记为TD(vi)。在有向图中，要区别顶点的入度和出度的概念在有向图中，要区别顶点的入度和出度的概念。所谓顶点所谓顶点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+21212（5）路径与回路：路径上边的数目称为）路径与回路：路径上边的数目称为路径长度路径长度。下图所示的无向图中，顶点下图所示的无向图中，顶点v1到顶点到顶点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都是连通的，则称无向都是连通的，则称无向图是连通的。无向图中极大连通子图称为连通分量。图是连通的。无向图中极大连通子图称为连通分量。对于有向图来说，图中任意一对顶点对于有向图来说，图中任意一对顶点vi和和vj(ij)均有从均有从vi到到vj及从及从vj到到vi的有向路径，则称该有向图是强连通的。的有向路径，则称该有向图是强连通的。有向图中的极大强连通子图称为该有向图的强连通分量。有向图中的极大强连通子图称为该有向图的强连通分量。1234123