数据结构第七章(图)

《数据结构第七章(图)》由会员分享，可在线阅读，更多相关《数据结构第七章(图)（46页珍藏版）》请在金锄头文库上搜索。

1、1青岛理工大学 通信与电子工程学院第7章 图7.1 图的定义和术语7.2 图的存储结构7.3 图的遍历7.4 图的应用 2青岛理工大学 通信与电子工程学院7.1 图的定义和术语l1、图、顶点、边l图G是由集合V(G)和E(G)组成,记为G=(V,E)，其中V(G)是顶 点的非空有限集合，E(G)是边的有限集合，边是顶点的无序对或有序对。l2、有向图、弧、无向图 245136G1l若图中的边是顶点的有序对，则称此图为有向图。l有向边又称为弧，通常用尖括号表示一条有向边，表示 从顶点v到w顶点的一条弧，v称为边的始点（或弧尾），w称 为边的终点（或弧头）。 3青岛理工大学 通信与电子工程学院例 2

2、45136G1l图G1中： V(G1)=1,2,3,4,5,6lE(G1)=, , , , , , 例 157324 G26l图G2中： V(G2)=1,2,3,4,5,6,7l无向图 若图中的边是顶点的无序对，则称此图为无向图。通 常用园括号表示无向边。（v,w）或（w,v)，并且（v,w)=(w,v)7.1 图的定义和术语lE(G1)=(1,2), (1,3), (2,3), (2,4),(2,5), (5,6), (5,7)4青岛理工大学 通信与电子工程学院l3、有向完全图、无向完全图l4、相邻顶点、相关联弧或边l无向完全图：n个顶点的无向图最大边数是n(n-1)/2，具有n(n -1)

3、/2条边的无向图称为无向完全图。213有向完全图213无向完全图7.1 图的定义和术语l若 E或(V1,V2) E ，则V1，V2是相邻顶点，弧 或边(V1,V2)是与顶点V1和V2相关联弧或边。 l有向完全图：具有n(n-1)条弧的有向图称为有向完全图。5青岛理工大学 通信与电子工程学院l5、度 例1 245136G1l顶点2入度：1 出度：3l顶点4入度：1 出度：0例2 157324G26l顶点5的度：3l顶点2的度：47.1 图的定义和术语l一个顶点V的度是与该顶点相关联的边的数目，记为TD（V）。l对于有向图，则把以顶点V为弧尾的数目称为点V的出度， 记为OD（V），把以顶点V为头的

4、弧的数目称为顶点V的入 度，记为ID（V）。 顶点V的度为：lTD（V）=ID（V）+OD（V） 6青岛理工大学 通信与电子工程学院l6、子图l设有两个图 G(V, E) 和 G(V, E)。若 V V 且 EE, 则称 图G 是 图G 的子图。7.1 图的定义和术语7青岛理工大学 通信与电子工程学院l7、路径l若一条路径上除了vi 和vj 可以相同外， 其余顶点均不相同， 则称此路径为一条简单路径 。7.1 图的定义和术语l在无向图 G(V, E) 中, 若存在一个顶点序列 vp1, vp2, , vpm， 使得(vi, vp1)、(vp1, vp2)、 .、(vpm, vj)均属于E，则称

5、顶点vi到vj存在一 条路径。路径长度定义为路径上边或弧的数目。l起点和终点相同的路径称为简单回路或简单环。8青岛理工大学 通信与电子工程学院例2157324G26例1245136G1l路径：1，2，3，5，6，3l路径：1，2，5，7，6，5，2，37.1 图的定义和术语l路径长度：5l简单路径：1，2，3，5l回路：1，2，3，5，6，3，1l简单回路：3，5，6，3l路径长度：7l简单路径：1，2，5，7，6l回路：1，2，5，7，6，5，2，1l简单回路：1，2，3，19青岛理工大学 通信与电子工程学院8、图的连通 在无向图G中，若两个顶点vi和vj之间有路径存在， 则称vi 和vj

6、是连通的。若G中任意两个顶点都是连通的，则称G为连通图。连通图例 245136 强连通图356例例 245136非连通图，连通分量9、强连通图与强连通分量 在有向图中, 若对于每一对顶点vi和 vj, 都存在一条从vi到vj和从vj到vi的路径,则称此图是强连通图。非强连通图的极大强连通子图叫做强连通分量。 7.1 图的定义和术语l非连通图的极大连通子图叫做连通分量。10青岛理工大学 通信与电子工程学院10、带权图或网12356874107966 71231516ABDCE60304535804075l若给图中每一条边附加一个实数作为权，则该图称 为带权图或网。7.1 图的定义和术语l这些权可

7、以表示从一个顶点到另一个顶点的距离 或花费的代价。11青岛理工大学 通信与电子工程学院一、图的数组(邻接矩阵)存储表示7.2 图的存储结构二、图的邻接表存储表示三、有向图的十字链表存储表示四、无向图的邻接多重表存储表示12青岛理工大学 通信与电子工程学院l用数组存储数据元素（顶点）的信息和数据元素之间的关 系（边或弧）的信息。 一、数组表示法（邻接矩阵）l在图的邻接矩阵表示中，有一个记录各个顶点信息的顶点 表，还有一个表示各个顶点之间关系的邻接矩阵。l设图 A = (V, E)是一个有 n 个顶点的图，则图的邻接矩阵定义：l无向图的邻接矩阵是对称的，有向图的邻接矩阵可能是不 对称的。13青岛理

8、工大学 通信与电子工程学院例G12413例15324 G2一、数组表示法（邻接矩阵）14青岛理工大学 通信与电子工程学院l借助邻接矩阵容易判定任意两个顶点之间是否有边（或弧）相连，并容易求得各个顶点的度。 l对于无向图，顶点Vi的度是邻接矩阵中第i行（或第i列）的元素之和，即 l对于有向图，第i行的元素之和为顶点Vi的出度OD（ Vi ），第j 列的元素之和为顶点Vj的入度ID(Vj)。一、数组表示法（邻接矩阵）例G1241315青岛理工大学 通信与电子工程学院l网的邻接矩阵可定义为：例1452375318642一、数组表示法（邻接矩阵）16青岛理工大学 通信与电子工程学院二、图的邻接表存储表

9、示q邻接表是图的一种链式存储结构。在邻接表中，对 图中每个顶点建立一个单链表，第i个单链表中的 结点表示依附于顶点Vi的边（对有向图中指以顶点 Vi为尾的弧）。adjvex nextarc infoq每个结点有三个域组成：q邻接结点域(adjvex)：指示与顶点Vi邻接的点在图 中的位置。q链域(nextarc)：指示下一条边或弧的结点。q数据域(info)：存储和边相关的信息，如权值等17青岛理工大学 通信与电子工程学院l每个链表上附设一个表头结点。在表头结点中，除了设有链域 (firstarc)指向链表中第一个结点之外，还设有存储顶点Vi的名 或其它有关信息的数据域(data)。头结点da

10、ta firstarc二、图的邻接表存储表示例V1V5V3V2V4 G20123V1V3V4V2vexdatafirstarc1423adjvexnext4V53204102118青岛理工大学 通信与电子工程学院l若无向图中有n个顶点、e条边，则它的邻接表需n个头结点 和2e个表结点。显然，在边稀疏(e，则Vj顶点的距离为此弧权值，否则为(一个很大的数)， 每次从W中选一个其距离值为最小的顶点Vm加入到S中，对W中的各个顶点的距离值进行一次修改。 若加进Vm做中间顶点，使+的值小于值，则用+代替原来Vj的距离，否则，什么也不做。 修改后再在W中选距离值最小的顶点加入到S中， 如此进行下去，直到

11、S中包含了图中所有顶点为止。41青岛理工大学 通信与电子工程学院迪杰斯特拉算法的求解过程：42青岛理工大学 通信与电子工程学院43青岛理工大学 通信与电子工程学院每对顶点之间的最短路径每对顶点之间的最短路径 顶点对之间的最短路径是指：对于给定的有向网G=(V,E),要对G中任意一对顶点有序对V、W(VW),找出V到W的最短距离。解决此问题的一个有效方法是:轮流以每一个顶点为源点,重复执行迪杰斯特拉算法n次,即可求得每一对顶点之间的最短路径,总 的时间复杂度为O(n3)。弗洛伊德提出了另外一个求图中任意两顶点之间最短路径的算 法，虽然其时间复杂度也是 O(n3)，但其算法的形式更简单，易于 理解

12、和编程。 44青岛理工大学 通信与电子工程学院弗洛伊德算法的基本思想是:设置一个nxn的矩阵A(k)，其中除对角线的元素都等于0外，其它元素a(k)ij表示顶点i 到顶点j的路径长度，K表示运算步骤。开始时，以任意两个顶点之间的有向边的权值作为路径长度，没有有向边时，路径长度为，当K=O时, A (0)ij=arcsij以后逐步尝试在原路径中加入其它顶点作为中间顶点，如果增加中间顶点后，得到的路径比原来的路径长度减少了，则 以此新路径代替原路径，修改矩阵元素。具体做法为： 45青岛理工大学 通信与电子工程学院第一步，让所有边上加入中间顶点1，取Aij与Ai1+A1j中较小的值作Aij的值，完成

13、后得到A(1)，第二步，让所有边上加入中间顶点2，取Aij与Ai2+A2j中较小的值，完成后得到A(2)，如此进行下去， 当第n步完成后，得到A(n)，A(n)即为我们所求结果,A(n)ij表示顶 点i到顶点j的最短距离。 因此，弗洛伊德算法可以描述为:A(0)ij=arcsij; /arcs为图的邻接矩阵A(k)ij=minA(k-1) ij,A(k-1) ik+A(k-1) kj其中 k=1,2,n46青岛理工大学 通信与电子工程学院FloydFloyd算法的基本思想：算法的基本思想：定义一个定义一个n n阶方阵序列：阶方阵序列：D D(-1)(-1), , D D(0)(0), , ,

14、, D D( (n-n-1)1). .其中其中 D D( (- -1) 1) i i j j = = G.arcsG.arcs i i j j ；D D( (k k) ) i i j j = min = min D D( (k k-1)-1) i i j j ，D D( (k k-1)-1) i i k k + + D D( (k k-1)-1) k k j j , , k k = 0,1, = 0,1, n n-1 -1 D D(0) (0) i i j j 是从顶点是从顶点v vi i 到到v vj j , , 中间顶点是中间顶点是v v0 0的最短路径的长度的最短路径的长度, , D D( (k k) ) i i j j 是从顶点是从顶点v vi i 到到v vj j , , 中间顶点的序号不大于中间顶点的序号不大于k k的最短路径长度的最短路径长度, , D D( (n-n-1)1) i i j j 是从顶点是从顶点v vi i 到到v vj j 的最短路径长度。的最短路径长度。