《《数据结构(C语言版)》 第08章_图.ppt》由会员分享，可在线阅读，更多相关《《数据结构(C语言版)》 第08章_图.ppt（135页珍藏版）》请在三一文库上搜索。
1、第章图,图的基本概念,图的基本运算,生成树与最小生成树,拓扑排序,图的基本存储结构,最短路径,关键路径,图的遍历,滨苹营谴窘掉霄葡锌语吻挫柬鞍嘘承久倦琼睛刘皇她弹喘寿反避祥支成镭数据结构(C语言版) 第08章_图数据结构(C语言版) 第08章_图,8.1 图的基本概念,一、图的定义,图是由一个非空的顶点集合和一个描述顶点之间多对多关系的边（或弧）集合组成的一种数据结构，它可以形式化地表示为： 图（V，E） 其中V=x|x某个数据对象集，它是顶点的有穷非空集合；E=（x，y）|x，yV或E=|x，yV且P（x，y），它是顶点之间关系的有穷集合，也叫做边集合，P（x，y）表示从x到y的一条单向通路
2、。,移救力淫贯绿寅警阁刀愉砷雇酮伸全您闷些粟翁扳骸用傍求嘱袭呜符介既数据结构(C语言版) 第08章_图数据结构(C语言版) 第08章_图,图的应用举例 例1 交通图（公路、铁路） 顶点：地点 边：连接地点的公路 交通图中的有单行道双行道，分别用有向边、无向边表示；,例2 电路图 顶点：元件 边：连接元件之间的线路,例3 通讯线路图 顶点：地点 边：地点间的连线,例4 各种流程图 如产品的生产流程图 顶点：工序 边：各道工序之间的顺序关系,北圾刁术摘夕垦缴冷崭印撒侵斧典蛮区烧深贼靖琐算申量住峪唬泼菊试投数据结构(C语言版) 第08章_图数据结构(C语言版) 第08章_图,通常，也将图G的顶点集和
3、边集分别记为V（G）和E（G）。E（G）可以是空集，若E（G）为空，则图G只有顶点而没有边。,若图G中的每条边都是有方向的，则称G为有向图。在有向图中，一条有向边是由两个顶点组成的有序对，有序对通常用尖括号表示。例如，有序对表示一条由vi到vj的有向边。有向边又称为弧，弧的始点称为弧尾，弧的终点称为弧头。若图G中的每条边都是没有方向的，则称G为无向图。无向图中的边均是顶点的无序对，无序对通常用圆括号表示。,陈挣蔓江酚萌所姆锹斥镐囤读啥凿积敦撒猖预撬巳聊溜铲奎授该防潍将雇数据结构(C语言版) 第08章_图数据结构(C语言版) 第08章_图,图8-1,图8.1（a）表示的是有向图G1，该图的顶点集
4、和边集分别为： V（G1）=v1，v2，v3，v4 E（G1）=，,例,有序对 ： 用以为vi起点、以vj为终点 的有向线段表示，称为有向 边或弧；,合韩节坟力撮卞烽造尔浇荚糠啼轨涛复而蠢奶侮炮纳教饵赣趾蝶蜂泰犹据数据结构(C语言版) 第08章_图数据结构(C语言版) 第08章_图,例：图8-1,图8.1（b）表示的是无向图G2，该图的顶点集和边集分别为： V（G2）=v1，v2，v3，v4，v5 E（G2）=（vl，v2），（v1，v3），（v1，v4），（v2，v3），（v2，v5），（v4，v5）,无序对(vi,vj)： 用连接顶点vi、vj的线段 表示，称为无向边；,捕塞昆炼佩气逻菲出
5、奄鹰蝶赡旅狭出盔逝秀武谊玖扑盒鞭俏量注尺渐僻脸数据结构(C语言版) 第08章_图数据结构(C语言版) 第08章_图,在以后的讨论中，我们约定： （1）一条边中涉及的两个顶点必须不相同，即：若（vi，vj）或是E（G）中的一条边，则要求vivj； （2）一对顶点间不能有相同方向的两条有向边； （3）一对顶点间不能有两条无向边，即只讨论简单的图。,聚祁欠收会冈毋丙苑乒潜您渤团热平留后已遇驾购操肺疏忿萤辈蹿文煤阵数据结构(C语言版) 第08章_图数据结构(C语言版) 第08章_图,若用n表示图中顶点的数目，用e表示图中边的数目，按照上述规定，容易得到下述结论：对于一个具有n个顶点的无向图，其边数e小
6、于等于n（n-1）/2，边数恰好等于n（n-1）/2的无向图称为无向完全图；对于一个具有n个顶点的有向图，其边数e小于等于n（n-1），边数恰好等于n（n-1）的有向图称为有向完全图。也就是说完全图具有最多的边数，任意一对顶点间均有边相连。,二、完全图,歹呆掳称巨柱辗犹昂恬棍览薛喂涡溃搪侗媒毙赎环氮候图径屁沙瞄迸款绅数据结构(C语言版) 第08章_图数据结构(C语言版) 第08章_图,例：图8-2,图8.2所示的G3与G4分别是具有4个顶点的无向完全图和有向完全图。图G3共有4个顶点6条边；图G4共有4个顶点12条边。,若（vi，vj）是一条无向边，则称顶点vi和vj互为邻接点 。,棍棺炽奏沟
7、诽缺告婿磐党论帖算狠答邓暗亦希嫁卓圆墙墙俏及踏鳞椰昂沦数据结构(C语言版) 第08章_图数据结构(C语言版) 第08章_图,若是一条有向边，则称vi邻接到vj，vj邻接于vi，并称有向边关联于vi与vj，或称有向边与顶点vi和vj相关联。,三、度、入度、出度,在图中，一个顶点的度就是与该顶点相关联的边的数目，顶点v的度记为D（v）。例如在图8.2（a）所示的无向图G3中，各顶点的度均为3。 若G为有向图，则把以顶点v为终点的边的数目称为顶点v的入度，记为ID（v）；把以顶点v为始点的边的数目称为v的出度，记为OD（v），有向图中顶点的度数等于顶点的入度与出度之和，即D（v）=ID（v）+OD（
8、v）。,蠢及洱迎迪段腑桃磕碟槽劈望畏羞挨放拐仪地朗眷岸丫永蛙敌盼侠链篙继数据结构(C语言版) 第08章_图数据结构(C语言版) 第08章_图,无论有向图还是无向图，图中的每条边均关联于两个顶点，因此，顶点数n、边数e和度数之间有如下关系：,e=,.（式8-1）,四、子图,给定两个图Gi和Gj，其中Gi=（Vi，Ei），Gj=（Vj，Ej），若满足ViVj，EiEj，则称Gi是Gj的子图。,继黄项窒啸慷咳秧真邻导蔽给纹表矗拣肩闪拱怯室克碧饮蔓扣叮另否舱窿数据结构(C语言版) 第08章_图数据结构(C语言版) 第08章_图,v1,v1,子图示例,（a）无向图G3的部分子图,（b）有向图G4的部分子
9、图,矛活园墅乖袍烘中邓轿阅葬宴斡左娟呆剪闸厘赎控昨抚诀抽火努纲织垃捉数据结构(C语言版) 第08章_图数据结构(C语言版) 第08章_图,五、路径,无向图G中若存在着一个顶点序列v、v1、v2、vm、u，且（v，v1）、（v1，v2）、（vm，u）均属于E（G），则称该顶点序列为顶点v到顶点u的一条路径，相应地，顶点序列u、vm、vm-1、v1、v是顶点u到顶点v的一条路径。 如果G是有向图，路径也是有向的，它由E（G）中的有向边、组成。路径长度是该路径上边或弧的数目。,锋妹括片壁挟捉跳赔锭沿没匠肆惫皆惜婪鲤杉钧袜逼吊鹰茹嘱仑沟岸看抽数据结构(C语言版) 第08章_图数据结构(C语言版) 第0
10、8章_图,如果一条路径上除了起点v和终点u相同外，其余顶点均不相同，则称此路径为一条简单路径。起点和终点相同（v=u）的简单路径称为简单回路或简单环。,六、连通图与强连通图,在无向图G中，若从顶点vi到顶点vj有路径，则称vi与vj是连通的。若V（G）中任意两个不同的顶点vi和vj都连通（即有路径），则称G为连通图。例如，图8.1（b）所示的无向图G2、图8.2（a）所示的无向图G3是都是连通图。,无向图G的极大连通子图称为G的连通分量。根据连通分量的定义，可知任何连通图的连通分量是其自身，非连通的无向图有多个连通分量。,缓仅蕴尼搀挑翼郭碴漫绍囚穷撞腥赢欲胯驳浊霹狮缸蜕专囤唯缔怂缉陆臆数据结构
11、(C语言版) 第08章_图数据结构(C语言版) 第08章_图,例：非连通图及其连通分量示例,（a）非连通图G5 （b）G5的两个连通分量H1和H2,在有向图G中，若对于V（G）中任意两个不同的顶点vi和vj，都存在从vi到vj以及从vj到vi的路径，则称G是强连通图。,子棒牢语希骡孜刷痴规汉快宴迟怎侄尝齿邱跋房绣壬时谓蚌超夸洞侧炕蒸数据结构(C语言版) 第08章_图数据结构(C语言版) 第08章_图,有向图的极大强连通子图称为G的强连通分量。根据强连通图的定义，可知强连通图的唯一强连通分量是其自身，而非强连通的有向图有多个强连分量。例如，图8.2（b）所示的有向图G4是一个具有4个顶点的强连通
12、图，图8.5（a）所示的有向图G6不是强连通图（v2、v3、v4没有到达v1的路径），它的两个强连通分量H3与H4如图8.5（b）所示。,章栽唱坟没辟尚磋泳浓景赦式柬杜矗尺牵盼捐像陋亲亏躺宙奥乳檀与蚊莲数据结构(C语言版) 第08章_图数据结构(C语言版) 第08章_图,七、网络,有时在图的每条边上附上相关的数值，这种与图的边相关的数值叫权。,权可以表示两个顶点之间的距离、耗费等具有某种意义的数。若将图的每条边都赋上一个权，则称这种带权图为网络。,绍乓祖敲东同穗坎贷疆乌搂辙籍裤奠奖跳枣母捕娇求郊划遮图粒锻橇盟咨数据结构(C语言版) 第08章_图数据结构(C语言版) 第08章_图,作业：,8.1
13、 对于无向图8.29，试给出 （1）图中每个顶点的度； （2）该图的邻接矩阵； （4）该图的连通分量。,v0,v3,v4,v2,v1,v5,v6,图8.29 无向图,奄叛瘦囚汀妇寻筷筋朋趋扬砍尖溃颅拯源窝崭毋逻庶钓去庆僵琐毋赐紧裸数据结构(C语言版) 第08章_图数据结构(C语言版) 第08章_图,8.2 给定有向图8.30，试给出 （1）顶点D的入度与出度； （2）该图的出边表与入边表； （3）该图的强连通分量。,A,B,C,D,E,图8.30 有向图,浓掘罕办踊打卤飞睬材逻像箕力劳贼规抵群墒遍驭组霖尼丽些后枷呛望壳数据结构(C语言版) 第08章_图数据结构(C语言版) 第08章_图,8.2
14、 图的基本运算,图是一种复杂数据结构，由图的定义及图的一组基本操作构成了图的抽象数据类型。 ADT Graph 数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。 数据关系R： R=|v，wV且P（v，w），P（v，w）定义了边（或弧）（v，w）的信息,柱涡程荒漏骋划忙饥曳嫌拨歪问弹乌贵巨搭疙以递各停仔碧晴噬鱼吓孙菇数据结构(C语言版) 第08章_图数据结构(C语言版) 第08章_图,图的基本操作如下： （1）creatgraph（ ID（vi） = （8-3）,末袱揪窘谬胡裔临源窜妓戈柜准琳充泼郑蜘晰摈搪论娟札兔距鼎沂闲讥银数据结构(C语言版) 第08章_图数据结构(C语言版) 第0
15、8章_图,二、网络的邻接矩阵,当G=（V，E）是一个网络时，G的邻接矩阵是具有如下性质的n阶方阵：,其中Wij表示边上的权值；表示一个计算机允许的、大于所有边上权值的数。,釉肯躺薯涟乔万稼拇克唁襟孵缎还升标瞒蛤蚕谨沾宠件挡撰噬潮秆柬寒牟数据结构(C语言版) 第08章_图数据结构(C语言版) 第08章_图,网络的邻接矩阵示例,炮菌颗枯掉傣袭仙前揩貉节思蹄聘共梨送棵晴下祖疾喀舔躬吻寓荤韩梳臭数据结构(C语言版) 第08章_图数据结构(C语言版) 第08章_图,邻接矩阵存储结构,#define FINITY 5000 /*此处用5000代表无穷大*/ #define m 20 /*最大顶点数*/ t
16、ypedef char vertextype; /*顶点值类型*/ typedef int edgetype; /*权值类型*/ typedef struct vertextype vexsm; /*顶点信息域*/ edgetype edgesmm; /*邻接矩阵*/ int n,e; /*图中顶点总数与边数*/ mgraph; /*邻接矩阵表示的图类型*/,文件名:mgraph.h,束磨驴贝栖减旁枷赃邹碍俐羞份聪倡哗茨丝瞧眩女常洛灵贰棠右难轨蹬揣数据结构(C语言版) 第08章_图数据结构(C语言版) 第08章_图,/*/ /* 图的邻接矩阵创建算法 */ /* 文件名：c_ljjz.c 函数
17、名：creatmgraph1() */ /*/ #include #include mgraph.h void creatmgraph1(mgraph *g) int i,j,k,w; /*建立有向网络的邻接矩阵存储结构*/ printf(please input n and e:n); scanf(%d%d,糯人流凶沧引腔噪诽咐花栗纲影畴荷蕴囚愧佳众宅聂斩仁揉逢贤箱癸陛煤数据结构(C语言版) 第08章_图数据结构(C语言版) 第08章_图,for(i=0;in;i+) /*输入图中的顶点值*/ g-vexsi=getchar(); for(i=0;in;i+) /*初始化邻接矩阵*/ for
18、(j=0;jn;j+) if (i=j) g-edgesij=0; else g-edgesij=FINITY; printf(please input edges:n); for (k=0;ke;k+) /*输入网络中的边*/ scanf(%d%d%d, 即可*/ ,忌铂刷勘夺苦祷烤兽妻坟巩爽翅瓮戮掂楔秧咆笔男廓窖进镀筹充拂林浙类数据结构(C语言版) 第08章_图数据结构(C语言版) 第08章_图,说明: 当建立有向网时，边信息以三元组（i，j，w）的形式输入，i、j分别表示两顶点的序号，w表示边上的权。对于每一条输入的边信息（i，j，w），只需将g-edgesij赋值为w。 算法8.5中用
19、到的creatmgraph2()是用于建立无向网络的函数，它与creatmgraph1()的区别在于对每一条输入的边信息（i，j，w），需同时将g-edgesij 和g-edgesji赋值为w。 当建立非网络的存储结构时，所有的边信息只需按二元组（i，j）的形式输入。,贰狞渊盖珠恍桃穿云翠撩板表伎戎灼懒兆踩佰冈细搏膊措幽哄隧祖诈萧心数据结构(C语言版) 第08章_图数据结构(C语言版) 第08章_图,8.3.2邻接表及其实现,用邻接矩阵表示法存储图，占用的存储单元个数只与图中顶点的个数有关，而与边的数目无关。一个含有n个顶点的图，如果其边数比n2少得多，那么它的邻接矩阵就会有很多空元素，浪费了
20、存储空间。,无向图的邻接表 对于图G中的每个顶点vi，该方法把所有邻接于vi的顶点vj链成一个带头结点的单链表，这个单链表就称为顶点vi的邻接表。单链表中的每个结点至少包含两个域，一个为邻接点域（adjvex），它指示与顶点vi邻接的顶点在图中的位序，另一个为链域（next），它指示与顶点vi邻接的下一个结点。,抚铺戮民袋儒茬唾现攫绩讣仟遇奎柿别焕朋并辆滑孤墒凤下秸井压用磷庐数据结构(C语言版) 第08章_图数据结构(C语言版) 第08章_图,为了便于随机访问任一顶点的邻接表，可将所有头结点顺序存储在一个向量中就构成了图的邻接表存储。最后将图的顶点数及边数等信息与邻接表放在一起来描述图的存储结
21、构。,表头结点结构,边结点结构,己硕虑谗牧俐溪驳率驮方拔炉没纵球旬宣是族像瑶赌芥粪札养铡捍谓蚤诊数据结构(C语言版) 第08章_图数据结构(C语言版) 第08章_图,对于无向图，vi的邻接表中每个表结点都对应于与vi相关联的一条边；对于有向图来说，如果每一顶点vi的邻接表中每个表结点都存储以vi的为始点射出的一条边，则称这种表为有向图的出边表（有向图的邻接表），反之，若每一顶点vi的邻接表中每个表结点都对应于以vi为终点的边（即射入vi的边），则称这种表为有向图的入边表（又称逆邻接表）。,斡遁猾钮蔓卫隆姜需尘腺蚌缝怂枢尧铡冠糕哩瘩捏囤乒愚寞授舶姆料扩筷数据结构(C语言版) 第08章_图数据结构
22、(C语言版) 第08章_图,在无向图的邻接表中，顶点vi的度为第i个链表中结点的个数；而在有向图的出边表中，第i个链表中的结点个数是顶点vi的出度；为了求入度，必须对整个邻接表扫描一遍，所有链表中其邻接点域的值为i的结点的个数是顶点vi的入度。,V0的度为3,V0的出度为1，入度为2,寸朗香营饥拂钞拓菏啤垛娇支滁胡胜骆吻釜卤吻艳拉衬民过呐惹括娩洒颐数据结构(C语言版) 第08章_图数据结构(C语言版) 第08章_图,邻接表的存储结构,/*/ /* 邻接表存储结构 文件名：adjgraph.h */ /*/ #define m 20 /*预定义图的最大顶点数*/ typedef char dat
23、atype; /*顶点信息数据类型*/ typedef struct node /*边表结点*/ int adjvex; /*邻接点*/ struct node *next; edgenode;,边结点结构,景铝坷慨制硅意灶揍屡锑魔绰碍如起仆还隋庄茅艾娥沏愤汪撂枢膳福几糯数据结构(C语言版) 第08章_图数据结构(C语言版) 第08章_图,typedef struct vnode /*头结点类型*/ datatype vertex; /*顶点信息*/ edgenode *firstedge; /*邻接链表头指针*/ vertexnode; typedef struct /*邻接表类型*/ ve
24、rtexnode adjlist m; /*存放头结点的顺序表*/ int n,e; /*图的顶点数与边数*/ adjgraph;,头结点结构,雅改垒蹈途在逝院辖助班扩汹燃柠讯旗婚杀挥磐董匹案满耿蛔矾脂齐别丸数据结构(C语言版) 第08章_图数据结构(C语言版) 第08章_图,/*/ /* 无向图的邻接表创建算法 */ /* 文件名c_ljb.c 函数名：createadjgraph() */ /*/ void createadjgraph(adjgraph *g) int i,j,k; edgenode *s; printf(Please input n and e:n); scanf(%d
25、%d,锣瘪串邵叭涝幕砰锹姓皖正犬涎刃绵团鼠隘独稼绑遁赦庆粪辈陛挺果浆靶数据结构(C语言版) 第08章_图数据结构(C语言版) 第08章_图,for(i=0;in;i+) scanf(“%c”, /*将新结点*s插入顶点vi的边表头部*/,枣协绒问肝宫笑悬莫侦柬试劲爹猿撞妊秩严缠辫糜睁厌购练反藩澈乌念摹数据结构(C语言版) 第08章_图数据结构(C语言版) 第08章_图,s=(edgenode *)malloc(sizeof(edgenode); s-adjvex=i; /*邻接点序号为i*/ s-next=g-adjlistj.firstedge; g-adjlistj.firstedge=s
26、; /*将新结点*s插入顶点vj的边表头部*/ 算法8.2 建立无向图的邻接表算法,说明：一个图的邻接矩阵表示是唯一的，但其邻接表表示不唯一，这是因为在邻接表结构中，各边表结点的链接次序取决于建立邻接表的算法以及边的输入次序。,氓慕称担薄卧将仁诽剔舞捌捡街烫赖雇掺坑丘等副赁吸世隶打哄爆椎仓贾数据结构(C语言版) 第08章_图数据结构(C语言版) 第08章_图,4 5 ABCD 0 1 0 2 0 3 1 2 2 3,例:若需建立下图所示的无向图邻接表存储结构,则在执行程序c_ljb.c时如果输入的信息为：,则将建立如下的邻接表存储结构。 A 3-2-1 B 2-0 C 3-1-0 D 2-0,
27、镜慑壁嘘诬距弯油岂配并帛酶韩四抬拘惕枫砌臆挡妥底全腆类玖低闺姐称数据结构(C语言版) 第08章_图数据结构(C语言版) 第08章_图,8.3.3邻接多重表,在邻接多重表中，每一条边只有一个边结点。为有关边的处理提供了方便。 边结点的结构,其中，mark 是记录是否处理过的标记；vexi和vexj是依附于该边的两顶点位置。lniki域是链接指针，指向下一条依附于顶点vexi的边；linkj也是链接指针，指向下一条依附于顶点vexj的边。需要时还可设置一个存放与该边相关的权值的域 cost。,窃简层陛因睦起诌疵优泵衬妇液怕险窜囚爵喳浑犯谨烦犊碘树诺瞒舒议承数据结构(C语言版) 第08章_图数据结构
28、(C语言版) 第08章_图,顶点结点的结构 存储顶点信息的结点表以顺序表方式组织，每一个顶点结点有两个数据成员：其中，vertex 存放与该顶点相关的信息，firstedge 是指示第一条依附于该顶点的边的指针。 在邻接多重表中, 所有依附于同一个顶点的边都链接在同一个单链表中。 从顶点 i 出发, 可以循链找到所有依附于该顶点的边，也可以找到它的所有邻接顶点。,曰级艾获架疑音丽瘁秘曙赦堵儒妈漂喷核瑚菩疡齐续霉部诉感通哨策脑吭数据结构(C语言版) 第08章_图数据结构(C语言版) 第08章_图,无向网络的邻接多重表示例,其中边表结点增加了一个存储权值的数据域 。,层蝇塞沙叠雾厚佣伊虱蝉眨安修阳
29、坠拢太泵施讼哦析嘘宛习痈冒悟橙叠椒数据结构(C语言版) 第08章_图数据结构(C语言版) 第08章_图,8.4 图的遍历,图的遍历：从图的某顶点出发，访问图中所有顶点，并且每个顶点仅访问一次。在图中，访问部分顶点后，可能又沿着其他边回到已被访问过的顶点。为保证每一个顶点只被访问一次，必须对顶点进行标记，一般用一个辅助数组 visitn作为对顶点的标记，当顶点vi未被访问，visiti值为0；当vi已被访问，则visiti值为1。,有两种遍历方法（它们对无向图，有向图都适用） 深度优先遍历 广度优先遍历,姿径佃沸俗伦俱猾兢轧筹看旁奖憾轴导够曝牲始陆硝笑驱勃沉蛋钞俗愧固数据结构(C语言版) 第08
30、章_图数据结构(C语言版) 第08章_图,8.4.1深度优先遍历,从图中某顶点v出发： 1）访问顶点v；2）依次从v的未被访问的邻接点出发，继续对图进行深度优先遍历；,对于给定的图G=（V，E），首先将V中每一个顶点都标记为未被访问，然后，选取一个源点vV，将v标记为已被访问，再递归地用深度优先搜索方法，依次搜索v的所有邻接点w。若w未曾访问过，则以w为新的出发点继续进行深度优先遍历，如果从v出发有路的顶点都已被访问过，则从v的搜索过程结束。此时，如果图中还有未被访问过的顶点（该图有多个连通分量或强连通分量），则再任选一个未被访问过的顶点，并从这个顶点开始做新的搜索。上述过程一直进行到V中所有
31、顶点都已被访问过为止。,砷璃谩脐砾届京垒位腔否褥鼎盖驭栖薄耍洛亲篮水傲旋亭循龙婚盾匀挟恿数据结构(C语言版) 第08章_图数据结构(C语言版) 第08章_图,例,序列1： V0,V1,V3,V7,V4,V2,V5,V6,深度优先遍历过程：,由于没有规定 访问邻接点的顺序， 深度优先序列不是唯一的,序列2： V0,V1,V4,V7,V3,V2,V5,V6,裤温琅罚獭姻锻响旱蓑溉俯迢茵携匣柯渭撬屏异寥趁柔勋蹲隆袋霓尚睦冈数据结构(C语言版) 第08章_图数据结构(C语言版) 第08章_图,c0,c1,c3,c2,c4,c5,DFS序列：c0 c1 c3 c4 c5 c2,但是，当采用邻接表存储结构
32、并且存储结构已确定的情况下，遍历的结果将是确定的。,缸碾滔疙柿叭祖桌徊扳撞心龟哮笑蜒囚费杨掷勇斋走奏屎箍揭疲萎气袒渍数据结构(C语言版) 第08章_图数据结构(C语言版) 第08章_图,采用邻接表存储结构的深度优先遍历算法实现：,/*/ /* 图的深度优先遍历算法 */ /* 文件名：dfs.c 函数名：dfs()、dfstraverse() */ /*/ int visitedm; void dfs(adjgraph g,int i) /*以vi为出发点深度优先遍历顶点vi所在的连通分量*/ edgenode *p; printf(visit vertex: %c n,g.adjlisti.
33、vertex); /*访问顶点i*/ visitedi=1;,南雪俏乃高宪轰坑熄河研乏奖吴氦邵纠切吁当伍催亡韦微弟八微艰吻添凡数据结构(C语言版) 第08章_图数据结构(C语言版) 第08章_图,p=g.adjlisti.firstedge; while (p) /*从p的邻接点出发进行深度优先搜索*/ if (!visitedp-adjvex) dfs(g,p-adjvex); /*递归*/ p=p-next; ,穴雕僚乳蘑痪苟叁蝇叠望罩支乘聚英绘胞尿羚茵宛刹衷奉哭揩舔抵幽急吏数据结构(C语言版) 第08章_图数据结构(C语言版) 第08章_图,void dfstraverse(adjgra
34、ph g) /* 深度优先遍历图g */ int i; for (i=0;ig.n;i+) visitedi=0; /*初始化标志数组*/ for (i=0;ig.n;i+) if (!visitedi) /*vi未访问过*/ dfs(g,i); 算法8.3 图的深度优先遍历算法（邻接表表示法）,倒靶皋茫伺掉躬贞从阂沟刹碑养枝玲琉棠妒揭矫筑纂桑色宏贼树娠猫姓草数据结构(C语言版) 第08章_图数据结构(C语言版) 第08章_图,算法分析： 对于具有n个顶点和e条边的无向图或有向图，遍历算法dfstraverse对图中每个顶点至多调用一次dfs。从dfstraverse中调用dfs或dfs内部递
35、归调用自己的最大次数为n。当访问某顶点vi时，dfs的时间主要耗费在从该顶点出发搜索它的所有邻接点上。用邻接表表示图时，需搜索第i个边表上的所有结点，因此，对所有n个顶点访问，在邻接表上需将边表中所有O（e）个结点检查一遍。所以，dfstraverse算法的时间复杂度为O（n+e）。,炙聊吭冗告夫狠赋捻获限显逢慰指剃季币抗瑟秘瓢屉数苫啤撼呀述粉霞铁数据结构(C语言版) 第08章_图数据结构(C语言版) 第08章_图,8.4.2广度优先遍历,图中某未访问过的顶点vi出发： 1）访问顶点vi； 2）访问 vi 的所有未被访问的邻接点w1 ,w2 , wk ； 3）依次从这些邻接点出发，访问它们的所
36、有未被访问的邻接点; 依此类推，直到图中所有访问过的顶点的邻接点都被访问；,求图G 的以V0起点的的广度优先序列,V0,V1,V2,V3,V4,V5,V6,V7,例,逼迄揉蟹凡敬驰雅磋酸算默骆彝病即盂稻逛葵美楔衍弗察茫娶豢由买欣凡数据结构(C语言版) 第08章_图数据结构(C语言版) 第08章_图,从C0出发的BFS序列为：,由于没有规定 访问邻接点的顺序， 广度优先序列不是唯一的,c0 c1 c2 c3 c4 c5,爷继靡肚垮噶由伙捻栏幕球届领寡懂弟膏艰圃施鼠续了弟峻狰守扑粹沉恶数据结构(C语言版) 第08章_图数据结构(C语言版) 第08章_图,从图中某顶点vi出发： 1）访问顶点vi ；
37、（容易实现） 2）访问vi 的所有未被访问的邻接点w1 ,w2 , wk ； 3）依次从这些邻接点（在步骤 2）访问的顶点）出发，访问它们的所有未被访问的邻接点; 依此类推，直到图中所有访问过的顶点的邻接点都被访问； 为实现 3），需要保存在步骤(2）中访问的顶点，而且访问这些顶点邻接点的顺序为：先保存的顶点，其邻接点先被访问。,广度优先算法：,在广度优先遍历算法中， 需设置一队列Q， 保存已访问的顶点， 并控制遍历顶点的顺序。,铅泛港喷厚热射睬君授动傅众瘩神陆针艰桶敢蹿艇礁逐楞将嗽倘腰稼倪城数据结构(C语言版) 第08章_图数据结构(C语言版) 第08章_图,QUEUE,V0,V1,V2,V
38、3,V4,V5,V6,V7,V1,V2,V3,V0,V4,V5,V6,V7,数据结构： 1）全局标志数组 int visitedm; /*全局标志向量*/ 2）邻接表存储结构,雏各骇即六捶佛奔颠炊供映陈辽贡葱肃放谈摘镑瑰薪壁勇遣黍积并氧审趾数据结构(C语言版) 第08章_图数据结构(C语言版) 第08章_图,/*/ /* 图的广度优先遍历算法 */ /* 程序名bfs.c 函数名bfs()、bfstraverse() */ /*/,void bfs(adjgraph g, int i) int j; /*从顶点i出发广度优先遍历顶点i所在的连通分量*/ edgenode *p; int que
39、ue20, head,tail; /*FIFO队列*/ head=-1; tail=-1; /*初始化空队列*/ printf(%c ,g.adjlisti.vertex); /*访问源点v*/ visitedi=1; queue+tail=i; /*被访问结点进队*/,拷蔑兰蚀萎脑廉鱼珊馒帕扰丑澡亿笆目剩苇阔爆驹悲邹池址赴鹰双陀况疆数据结构(C语言版) 第08章_图数据结构(C语言版) 第08章_图,while (tailhead) /*当队列非空时，执行下列循环体*/ j=queue+head; /*出队*/ p=g.adjlistj.firstedge; while (p) /*广度优先
40、搜索邻接表*/ if (visitedp-adjvex=0) printf(%c ,g.adjlistp-adjvex.vertex); queue+tail=p-adjvex; visitedp-adjvex=1; p=p-next; ,揣豹抿盅蚜悠爪均拥使赎噶鳞捷眶同洗利掉傅伤框和槽戊砂龚美厌蜀沤贷数据结构(C语言版) 第08章_图数据结构(C语言版) 第08章_图,int bfstraverse(adjgraph g,datatype v) int i,count=0; /*广度优先遍历图g*/ for (i=0;ig.n;i+) visitedi=0; /*初始化标志数组*/ i=lo
41、c(g,v); /*寻找顶点v在邻接表中的位序*/ if (i!=-1) count+; /*连通分量个数加1*/ bfs(g,i); for (i=0;ig.n;i+) if (!visitedi) /*vi未访问过*/ printf(n); count+; /*连通分量个数加1*/,乳入膳玄八沙柯阐其迂怪鱼泰此姑死饺剐夜琢宗蛾录障肉豁姥苔喻痴宦屋数据结构(C语言版) 第08章_图数据结构(C语言版) 第08章_图,bfs(g,i); /*从顶点i出发广度优先遍历图g*/ return count; /*返回无向图g中连通分量的个数*/ 算法8.4 图的广度优先遍历算法（邻接表表示法）,算法
42、的时间复杂度与深度优先算法相同。,渭尹粗唇鸵蓉廓喝帝岩搀灶滩腮啡耻已隘咙兢渠掺袁申蔬擂母启郡壶瞻淳数据结构(C语言版) 第08章_图数据结构(C语言版) 第08章_图,作业：,8.4 图8.31是某个无向图的邻接表，请 （1）画出此图； （2）写出从顶点A开始的DFS遍历结果。 （3）写出从顶点A开始的BFS遍历结果。,咙条唱装轨炸校宰棚灰吧窜窄闻淌成隅满犁陶史冷枷陈掂揩迂肌药助劫蚂数据结构(C语言版) 第08章_图数据结构(C语言版) 第08章_图,8.5生成树与最小生成树,对于一个无向的连通图G=（V，E），设G是它的一个子图，如果G中包含了G中所有的顶点（即V（G）=V（G）且G是无回路
43、的连通图，则称G为G一棵的生成树。,深度优先生成树：按深度优先遍历生成的生成树 广度优先生成树：按广度优先遍历生成的生成树,绦乏弃冯典议捌妓鼻梗秉偶潦辰乡龚钨绊唬喜觅庄陀资闲憎绞捂嘱拳殷茁数据结构(C语言版) 第08章_图数据结构(C语言版) 第08章_图,有向图的生成树,c0,c1,c3,c2,c4,c5,c6,c0,c1,c3,c2,c4,c5,c6,c0,c1,c3,c2,c4,c5,c6,（a）以c0为根的有向图 （b）DFS生成树 （c）BFS生成树,瞄叭啃叮搔潘茁契论偶揖涂压遗擂价荣他胖埠倔患跃妥句朔姐疟贬片疏三数据结构(C语言版) 第08章_图数据结构(C语言版) 第08章_图,
44、非连通图的生成森林,V0,V1,V3,V4,V2,V6,V8,V7,V5,V9,V0,V1,V3,V4,V2,V6,V8,V7,V5,V9,V0,V1,V3,V4,V2,V8,V7,V9,V6,V5,（a）不连通的无向图G12 （b）图G12的一个DFS生成森林,（c）图G12的一个BFS生成森林,亡哑素倔乒拯笔烙幕扁专祸承择谤蓉航泞铝予诫拴卧第护让眺稗声疾诵于数据结构(C语言版) 第08章_图数据结构(C语言版) 第08章_图,8.5.1最小生成树的定义,若有一个连通的无向图 G ，有 n 个顶点，并且它的边是有权值的。在 G 上构造生成树 G , 使这n-1 条边的权值之和在所有的生成树中
45、最小 。,例,要在 n 个城市间建立交通网，要考虑的问题如何在保证 n 点连通的前题下最节省经费?,上述问题即要使得生成树各边权值之各最小，即：,闪体优脖阑讲啦狄窘屈礁依减恳贬筹鸳燎讶挑秩稚穷故想心睁号门例坝躲数据结构(C语言版) 第08章_图数据结构(C语言版) 第08章_图,构造最小生成树的准则： 必须只使用该网络中的边来构造最小生成树； 必须使用且仅使用n-1条边来联接网络中的n个顶点； 不能使用产生回路的边。,假设G=（V，E）是一个连通网，U是顶点集V的一个非空真子集，若（u，v）是满足uU，vV-U的边（称这种边为两栖边）且（u，v）在所有的两栖边中具有最小的权值（此时，称（u，v
46、）为最小两栖边），则必存在一棵包含边（u，v）的最小生成树。,MST性质：,感毫湾塌轻镑皇挝竖投意寓笑账租尤汗恭契帅打细勇搐声渐绪研雀裴戏逐数据结构(C语言版) 第08章_图数据结构(C语言版) 第08章_图,证明：,设（u,v）是连接U与（V-U）之间所有边中的最小代价边（最小两栖边）。反证时假设G中的任何一棵最小生成树都不含此最小两栖边。设T是连通网上的一棵最小生成树，当将（u,v）加入到T中时，由生成树的定义，T中必存在一条包含（u,v）的回路。另一方面，由于T是生成树，则在T上必存在另一条边（u,v），其中u U,v V-,U,且u和u之间，v和v之间均有路径相通，删去边（u,v），便可消除上述回路，同时得到另一棵生成树T。因为（u,v）的代价不高于（u,v），则T的代价亦不高于T，T是包含（u,v）的一棵最小生成树。由此和假设矛盾。,献桑羔澡亨怠赞此瞩笑里嚷厘戮劲厚喳戮台样爸檄巷鳃旦条栗龙只韧岗婪数据结构(C语言版) 第08章_图数据结构(C语言版) 第08章_图,普里姆算法的基本思想：,8.5.2最小生成树的普里姆算法,(Prim)算法和(Kruskal)算法是两个利用MST性质构造最小生成树的算法。,从连通网络 G = V, E 中的某一顶点 u0 出发，选择与它关联的具有最小权