数据结构-第七章-图7.1课件.ppt

《数据结构-第七章-图7.1课件.ppt》由会员分享，可在线阅读，更多相关《数据结构-第七章-图7.1课件.ppt（39页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第七章第七章 图图 7.1 7.1 图的定义和术语图的定义和术语 7.2 7.2 图的存储结构图的存储结构 7.3 7.3 图的遍历图的遍历 7.4 7.4 图的连通性图的连通性 7.5 7.5 有向无环图及其应用有向无环图及其应用 7.6 7.6 最短路径最短路径 一、一、图的定义图的定义 图图由由两两个个集集合合V V和和E E构构成成，记记为为G=(V,E)G=(V,E)，其其中中V V是是顶顶点点的的有有限限集集合合，E E是是边边的的有有限限集集合合，边边是是顶顶点点的的无无序序对对或或有有序对。序对。7.1 7.1 图图的的定定义义和和术术语语1.1.有有向向图图：E E中中的的顶

2、顶点点对对是是有有序序的的，即即每每条条边边都都是是有有方方向向 的，则称的，则称G G为有向图。为有向图。2.2.弧弧：有向图的边：有向图的边，表示从，表示从v v到到w w的一条弧。的一条弧。3.3.弧头弧头：弧的终点：弧的终点w w。弧尾弧尾：弧的起始点：弧的起始点v v。4.4.无无向向图图：E E中中顶顶点点对对是是无无序序的的，则则称称G G为为无无向向图图。无无向向图的边用无序对图的边用无序对(v,w)(v,w)表示。表示。二、图的有关术语二、图的有关术语7.1 7.1 图图的的定定义义和和术术语语 用用n n表示图中顶点数目，用表示图中顶点数目，用e e表示边或弧的数目表示边或

3、弧的数目。5.5.完完全全图图：对对于于无无向向图图0en(n-1)/2,0en(n-1)/2,具具有有n(n-1)/2n(n-1)/2条条边边的无向图称为完全图。的无向图称为完全图。6.6.有有向向完完全全图图：对对于于有有向向图图0en(n-1)0en(n-1)，具具有有n(n-1)n(n-1)条条弧弧的有向图称为有向完全图。的有向图称为有向完全图。7.7.子子图图：有有两两个个图图G=(V,E)G=(V,E)和和G=(V,E)G=(V,E)，如如果果VV V V且且EE E E，则称，则称GG为为G G的子图。的子图。7.1 7.1 图图的的定定义义和和术术语语 二、图的有关术语二、图的

4、有关术语13.13.连连通通(可可及及)：在在图图G G中中，若若从从顶顶点点v v到到vv有有路路径径，则则称称v v和和vv是连通的是连通的(可及的可及的)。14.14.连连通通图图：在在无无向向图图G G中中，任任意意两两个个顶顶点点都都是是连连通通的的，称称图图G G是连通图。是连通图。15.15.连通分量：连通分量：无向图中的无向图中的极大连通子图极大连通子图。7.1 7.1 图图的的定定义义和和术术语语 二、图的有关术语二、图的有关术语16.16.强强连连通通图图：在在有有向向图图G G中中，对对于于任任意意两两个个不不同同顶顶点点vivi和和vjvj，vivi和和vjvj连通，连

5、通，vjvj和和vivi连通，称连通，称G G为强连通图。为强连通图。17.17.强强连连通通分分量量：有有向向图图中中的的极极大大连连通通子子图图称称作作有有向向图图的的强强连通分量。连通分量。7.1 7.1 图图的的定定义义和和术术语语 二、图的有关术语二、图的有关术语18.18.生成树生成树：一一个个连连通通图图的的生生成成树树是是一一个个极极小小连连通通子子图图，它它含含有有图图中全部顶点中全部顶点，但只有足以构成一棵树的，但只有足以构成一棵树的n-1n-1条边条边。说明：一棵有说明：一棵有n n个顶点个顶点的生成树有且仅有的生成树有且仅有n-1n-1条边；条边；一个图有一个图有n n

6、个顶点个顶点和和小于小于n-1n-1条边条边，则是则是非连通图；非连通图；一个图有一个图有n n个顶点个顶点和和大于大于n-1n-1条边条边，则则一定有环一定有环。注：一个图有注：一个图有n n个顶点和个顶点和n-1n-1条边，不一定是生成树，条边，不一定是生成树，必须保证连通。必须保证连通。7.1 7.1 图图的的定定义义和和术术语语 二、图的有关术语二、图的有关术语例例157324G26例例245136G1路径：1，2，3，5，6，3路径长度：5简单路径：1，2，3，5回路：1，2，3，5，6，3，1简单回路：3，5，6，3路径：1，2，5，7，6，5，2，3路径长度：7简单路径：1，2，

7、5，7，6回路：1，2，5，7，6，5，2，1简单回路：1，2，3，1356例例245136图与子图图与子图7.1 7.1 图图的的定定义义和和术术语语 二、图的有关术语二、图的有关术语 二、图的有关术语二、图的有关术语7.1 7.1 图图的的定定义义和和术术语语连通图连通图G1G1例例非连通图非连通图G2G2245136例例DEIGHK非连通图非连通图G2G2的三个连通分量的三个连通分量7.2 7.2 图的存储结构图的存储结构一、邻接矩阵（数组表示法）一、邻接矩阵（数组表示法）二、邻接表二、邻接表 例例1：如图所示的是：如图所示的是有向网有向网的邻接矩阵表示存储结构：的邻接矩阵表示存储结构：

8、7.2 7.2 图图的的存存储储结结构构G1.vexs=v0,v1,v2,v3,v4 0 1 2 3 40 2 7 11 2 5 3 4 3 4 G1.arcs=G1.vexnum=5G1.arcnum=6G1.kind=DN 一、邻接矩阵一、邻接矩阵例例2：无向图无向图的邻接矩阵表示存储结构：的邻接矩阵表示存储结构：7.2 7.2 图图的的存存储储结结构构G2.vexs=v1,v2,v3,v4 1 2 3 41 0 1 1 12 1 0 0 13 1 0 0 14 1 1 1 0G2.arcs=G2.vexnum=4G2.arcnum=5G2.kind=AG 一、邻接矩阵一、邻接矩阵 二、邻

9、接表二、邻接表7.2 7.2 图图的的存存储储结结构构1 1方法：类似于树的孩子链表表示法方法：类似于树的孩子链表表示法 将将每每个个顶顶点点的的所所有有邻邻接接点点排排列列起起来来，构构成成一一个个线线性表，且以性表，且以单链表作存储结构单链表作存储结构 n n个顶点有个顶点有n n个单链表，个单链表，n n个表头结点又组成一个个表头结点又组成一个线性表线性表(采用顺序存储采用顺序存储)。7.2 7.2 图图的的存存储储结结构构例例G1bdac例例aecbdG20123acdbdatafirstarc 21 3 0adjvex nextarc0123acdbdatafirstarc 1 42

10、 3adjvex nextarc4e 3 2 0 41 02 1 二、邻接表二、邻接表2 2邻接表的性质邻接表的性质(1)(1)无无向向图图的的邻邻接接表表中中第第i i个个顶顶点点的的度度为为第第i i个个链链表表中中结结点点的的个数；个数；(2)(2)有有向向图图的的邻邻接接表表中中第第i i个个链链表表的的结结点点的的个个数数是是第第i i个个顶顶点点的的出出度度；而而第第i i个个顶顶点点的的入入度度需需遍遍历历整整个个链链表表，采采用用逆逆邻邻接接表表,建立一个以建立一个以vivi顶点为弧头的表。顶点为弧头的表。(3)(3)无无向向图图的的边边数数等等于于邻邻接接表表中中表表结结点点

11、个个数数的的一一半半，有有向向图图的弧数的弧数等于邻接表中表结点的个数等于邻接表中表结点的个数。7.2 7.2 图图的的存存储储结结构构 二、邻接表二、邻接表7.3 7.3 图的遍历图的遍历一、深度优先搜索一、深度优先搜索二、广度优先搜索二、广度优先搜索 图图的的遍遍历历从从图图的的某某一一顶顶点点出出发发访访问问图图中中的的所所有有顶点，且每个顶点仅访问一次。顶点，且每个顶点仅访问一次。一、深度优先搜索一、深度优先搜索7.3 7.3 图图的的遍遍历历1.1.深度优先搜索深度优先搜索(Depth First Search)(Depth First Search)算法的基本思想算法的基本思想(1

12、)(1)首先访问图中某一个顶点首先访问图中某一个顶点V Vi i，以该顶点为，以该顶点为出发点出发点；(2)(2)任选一个与顶点任选一个与顶点ViVi邻接邻接的的未被访问未被访问的顶点的顶点VjVj；(3)(3)以以VjVj为为新新的的出出发发点点继继续续进进行行深深度度优优先先搜搜索索，直直至至图图中中所有和所有和V Vi i有路径的顶点均被访问到。有路径的顶点均被访问到。若此时图中尚有顶点未被访问，则另选图中一个未被若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作起始点，重复上述过程，直至图中所有顶点访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到。都被访问到。注：注

13、：若深度优先搜索时只进行若深度优先搜索时只进行(1)(2)(3)(1)(2)(3)步，便访问到步，便访问到了图中的所有顶点，则该图为了图中的所有顶点，则该图为连通图连通图，否则为非连通图。，否则为非连通图。1.1.广度优先搜索广度优先搜索(Breadth First Search)Breadth First Search)算法基本思想算法基本思想2.2.(1)(1)首先访问图中某一个指定的首先访问图中某一个指定的出发点出发点vivi；3.3.(2)(2)然后依次访问然后依次访问vivi的所有的所有邻接点邻接点vi1,vi2vi1,vi2vitvit；4.4.(3)(3)再再依依次次以以vi1,

14、vi2vi1,vi2vitvit为为顶顶点点，访访问问各各顶顶点点未未被被访访问问的邻接点，依此类推，直到图中所有顶点均被访问为止。的邻接点，依此类推，直到图中所有顶点均被访问为止。二、广度优先搜索二、广度优先搜索7.3 7.3 图图的的遍遍历历2 2广度优先搜索的例子广度优先搜索的例子7.3 7.3 图图的的遍遍历历V1V2V4V5V3V7V6V8广度遍历广度遍历：V1 V2 V3 V4 V5 V6 V7 V8例例 二、广度优先搜索二、广度优先搜索2 2广度优先搜索的例子广度优先搜索的例子Q F F F F F F F F FVisitv 0 1 2 3 4 5 6 7 8 出发点出发点TV

15、1V1TV2TV6V2TV3V7TV6TTV5V3TTV4V8V7TTTV9V4V5V8V97.3 7.3 图图的的遍遍历历 二、广度优先搜索二、广度优先搜索7.4 7.4 图的连通性问题图的连通性问题 利用遍历图的算法求解图的连通性问题。本节主利用遍历图的算法求解图的连通性问题。本节主要介绍要介绍无向图的连通分量无向图的连通分量和和生成树的生成生成树的生成以及以及最小生最小生成树问题。成树问题。一、无向图的连通分量和生成树一、无向图的连通分量和生成树 二、最小生成树二、最小生成树 一、一、无向图无向图的连通分量和生成树的连通分量和生成树7.47.4图图的的连连通通性性问问题题1.1.连通图的

16、生成树连通图的生成树 由由由由遍遍遍遍历历历历连连连连通通通通图图图图G G G G时时时时所所所所经经经经过过过过的的的的边边边边和和和和顶顶顶顶点点点点构构构构成成成成的的的的子子子子图是图是图是图是G G G G的生成树。的生成树。的生成树。的生成树。由深度优先搜索得到的是深度优先搜索生成树；由深度优先搜索得到的是深度优先搜索生成树；由广度优先搜索得到的是广度优先搜索生成树。由广度优先搜索得到的是广度优先搜索生成树。一、一、无向图无向图的连通分量和生成树的连通分量和生成树7.47.4图图的的连连通通性性问问题题2 2 非连通图的生成森林非连通图的生成森林 由由遍遍历历非非连连通通图图G时

17、时所所经经过过的的边边和和顶顶点点构构成成若若干干个个生生成成树树（连连通通分分量量），这这些些连连通通分分量量的的生生成成树树组组成成非非连连通通图图的生成森林的生成森林。一、一、无向图无向图的连通分量和生成树的连通分量和生成树7.47.4图图的的连连通通性性问问题题ABLMCFDEGHKIJABLMCFJDEGHKI深度优先生成森林深度优先生成森林例例1.1.最小生成树的定义最小生成树的定义 二、最小生成树二、最小生成树7.47.4图图的的连连通通性性问问题题1654327131791812752410要在要在n n个城市间建立通信联络网，个城市间建立通信联络网，顶点顶点表示城市表示城市边

18、的权边的权城市间建立通信线路所需花费代价城市间建立通信线路所需花费代价希望找到一棵生成树，其代价最小希望找到一棵生成树，其代价最小最小代价生成树最小代价生成树问题提出问题提出最小生成树：最小生成树：如果无向连通图是一个网，那么它的所如果无向连通图是一个网，那么它的所有生成树中必有一棵边的权值总和最小的生成树，称为有生成树中必有一棵边的权值总和最小的生成树，称为最小代价生成树，简称最小生成树最小代价生成树，简称最小生成树 二、最小生成树二、最小生成树7.47.4图图的的连连通通性性问问题题2 2 构造最小生成树方法构造最小生成树方法方法一：普里姆方法一：普里姆(Prim)(Prim)算法算法算法

19、思想算法思想：设：设N=(V,E)N=(V,E)是具有是具有n n个顶点的个顶点的连通网连通网，T=(U,TE)T=(U,TE)是是N N的最小生成树：的最小生成树：1 1）初始令）初始令U=u0,(u0U=u0,(u0 V),TE=V),TE=2 2）在所有在所有u u U U，v v V-UV-U的边（的边（u,vu,v）E E中，找一条中，找一条代价最小的边代价最小的边(u0,v0)u0,v0)3 3）将将(u0,v0)u0,v0)并入集合并入集合TETE，同时同时v0v0并入并入U U4 4）重复上述重复上述2 2）、）、3 3）步操作）步操作直至直至U=VU=V为止，此时为止，此时T

20、ETE 中含有中含有n-1n-1条边，且条边，且T=(V,TE)T=(V,TE)即为即为N N的最小生成树的最小生成树例例1654326513566425131163141643142116432142516543214253 二、最小生成树二、最小生成树7.47.4图图的的连连通通性性问问题题 二、最小生成树二、最小生成树7.47.4图图的的连连通通性性问问题题 二、最小生成树二、最小生成树7.47.4图图的的连连通通性性问问题题方法二：克鲁斯卡尔方法二：克鲁斯卡尔(Kruskal)(Kruskal)算法算法算法思想算法思想：设：设连通网连通网N=(V,E)N=(V,E)，T=(U,TE)T

21、=(U,TE)是最小生成树是最小生成树 初始状态为只有初始状态为只有n n个顶点而无边的非连通图个顶点而无边的非连通图T=(T=(V V,)，即，即U=VU=V，TE=TE=,图中每个顶点自成一个图中每个顶点自成一个连通分量。连通分量。在在E E中选取代价最小的边，若中选取代价最小的边，若该边依附的顶点落在该边依附的顶点落在T T中不同的连通分量上中不同的连通分量上，则将此边加入到，则将此边加入到T T中；否则，中；否则，舍去此边，选取下一条代价最小的边，依此类推，直舍去此边，选取下一条代价最小的边，依此类推，直至至T T中所有顶点都在同一连通分量上为止，此时中所有顶点都在同一连通分量上为止，此时T T即为即为最小生成树。最小生成树。二、最小生成树二、最小生成树7.47.4图图的的连连通通性性问问题题165432651356642516543212345例例 二、最小生成树二、最小生成树7.47.4图图的的连连通通性性问问题题