第八章 图.ppt

《第八章 图.ppt》由会员分享，可在线阅读，更多相关《第八章 图.ppt（37页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构（Java语言版）邮箱：第8章 图教师:温荷8.1 实例引入 【例8.1】北京及周边部分城市交通图。如图8.1所示为北京及周边地区交通示意图，从图中可看出，北京市、天津市、承德市、唐山市、保定市、沧州市、廊坊市、张家口市相互之间都可以连通，选取其中五个城市及部分线路，抽象出如图8.2所示的交通路线图，其对应关系为北京市(A)、承德市(B)、唐山市(C)、保定市(D)、张家口市(E)。图8.1 北京及周边部分城市交通示意图 从图中可以看出，五个城市之间都有互相连通的道路，形成了一个多对多的关系，也称为图形关系，或者网状关系。ACBED图8.2 北京周边地区交通模拟示意图第六章 图图的定义

2、和术语v图(Graph)图G是由两个集合V(G)和E(G)组成的,记为G=(V,E)其中：V(G)是顶点的非空有限集 E(G)是边的有限集合，边是顶点的无序对或有序对v有向图有向图G是由两个集合V(G)和E(G)组成的 其中：V(G)是顶点的非空有限集 E(G)是有向边（也称弧）的有限集合，弧是顶点的有序对，记为，v,w是顶点，v为弧尾，w为弧头v无向图无向图G是由两个集合V(G)和E(G)组成的 其中：V(G)是顶点的非空有限集 E(G)是边的有限集合，边是顶点的无序对，记为（v,w）或（w,v)，并且（v,w)=(w,v)例245136G1图G1中：V(G1)=1,2,3,4,5,6 E(

3、G1)=,例157324G26图G2中：V(G2)=1,2,3,4,5,6,7 E(G1)=(1,2),(1,3),(2,3),(2,4),(2,5),(5,6),(5,7)v有向完备图n个顶点的有向图最大边数是n(n-1)v无向完备图n个顶点的无向图最大边数是n(n-1)/2v权与图的边或弧相关的数叫v网带权的图叫v子图如果图G(V,E)和图G(V,E),满足：lVVlEE 则称G为G的子图v顶点的度l无向图中，顶点的度为与每个顶点相连的边数l有向图中，顶点的度分成入度与出度u入度：以该顶点为头的弧的数目u出度：以该顶点为尾的弧的数目例213213有向完备图无向完备图356例245136图与

4、子图例245136G1顶点2入度：1 出度：3顶点4入度：1 出度：0例157324G26顶点5的度：3顶点2的度：4v路径路径是顶点的序列V=Vi0,Vi1,Vin，满足(Vij-1,Vij)E 或 E,(1w1,V-w2,V-w8 的路径长度为1;V-w7,V-w3,V-w5 的路径长度为2;V-w6,V-w4 的路径长度为3。w1Vw2w7w6w3w8w5w4 V W1W2W8W7W3W5W6W4V1V2V4V5V3V7V6V8例例V1V2V4V5V3V7V6V8广度遍历：V1 V2 V3 V4 V5 V6 V7 V8广度遍历：V1 V2 V3 V4 V5 V6 V7 V8V1V2V4V

5、5V3V7V6V8例广度遍历：V1 V2 V3 V4 V6 V7 V8 V56.4 生成树生成树v定义：所有顶点均由边连接在一起，但不存在回路的图叫v深度优先生成树与广度优先生成树v生成森林：非连通图每个连通分量的生成树一起组成非连通图的v说明l一个图可以有许多棵不同的生成树l所有生成树具有以下共同特点：u生成树的顶点个数与图的顶点个数相同u生成树是图的极小连通子图u一个有n个顶点的连通图的生成树有n-1条边u生成树中任意两个顶点间的路径是唯一的u在生成树中再加一条边必然形成回路l含n个顶点n-1条边的图不一定是生成树GHKIV1V2V4V5V3V7V6V8例深度遍历：V1 V2 V4 V8

6、V5 V3 V6 V7V1V2V4V5V3V7V6V8深度优先生成树V1V2V4V5V3V7V6V8广度优先生成树V1V2V4V5V3V7V6V8V1V2V4V5V3V7V6V8广度遍历：V1 V2 V3 V4 V5 V6 V7 V8例ABLMCFDEGHKIJABLMCFJDEGHKI深度优先生成森林最小生成树v问题提出要在n个城市间建立通信联络网，顶点表示城市权城市间建立通信线路所需花费代价希望找到一棵生成树，它的每条边上的权值之和（即建立该通信网所需花费的总代价）最小最小代价生成树v问题分析1654327131791812752410n个城市间，最多可设置n(n-1)/2条线路n个城市间

7、建立通信网，只需n-1条线路问题转化为：如何在可能的线路中选择n-1条，能把 所有城市（顶点）均连起来，且总耗费 （各边权值之和）最小v构造最小生成树方法l方法一：普里姆(Prim)算法u算法思想：设N=(V,E)是连通网，TE是N上最小生成树中边的集合Y初始令U=u0,(u0V),TE=Y在所有uU,vV-U的边(u,v)E中，找一条代价最小的边(u0,v0)Y将(u0,v0)并入集合TE，同时v0并入UY重复上述操作直至U=V为止，则T=(V,TE)为N的最小生成树u算法实现：图用邻接矩阵表示u算法描述u算法评价：T(n)=O(n)例1654326513566425131163141643

8、142116432142516543214253abcdegf195141827168213127例如例如:aedcbgf148531621所得生成树权值和=14+8+3+5+16+21=67l方法二：克鲁斯卡尔(Kruskal)算法u算法思想：设连通网N=(V,E)，令最小生成树Y初始状态为只有n个顶点而无边的非连通图T=(V,)，每个顶点自成一个连通分量Y在E中选取代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中；否则，舍去此边，选取下一条代价最小的边Y依此类推，直至T中所有顶点都在同一连通分量上为止例165432651356642516543212345例如例如:5148213aedcbgfabcdegf19514627168213ae12dcbgf76