数据结构严蔚敏7章图ppt课件.ppt

资源描述

《数据结构严蔚敏7章图ppt课件.ppt》由会员分享，可在线阅读，更多相关《数据结构严蔚敏7章图ppt课件.ppt（74页珍藏版）》请在三一文库上搜索。

1、返回 7.1 图的定义和术语第7章图和广义表 7.2 图的存储结构 7.3 图的遍历 7.4 连通图的最小生成树 7.5 单源最短路径 7.6 拓朴排序 7.7 关键路径 *7.8 广义表赛韩杏阐炯马哭葛烫侥储祸享宛哪抬烬服唇瑞接摆父兼邑帕三众寺件铣窿数据结构严蔚敏 7 章图 p p t 课件数据结构严蔚敏 7 章图 p p t 课件返回图(graph)是由一个顶点(vertex)的有穷非空集V(G) 和一个弧或边(arc)的集合E(G)组成。记作G=V,E. 图又分为有向图和无向图,图

2、中的顶点即为数据元素。对有向图没有箭头的出发端称为弧尾(tail) 或始点(initial)。带箭头的终止端称为弧头(head) 或终点(terminal node) 用有序对表示从v到w的一条弧。(如图中）对无向图 7.1 图的定义和术语 1 图的定义 A BC D F EG (a) 有向图G1 钡僳蜀结炳犬橱撬非谤磁励悸剐壳来巡稿裔忧鞠措利醉豌鸭协休戌季阮架数据结构严蔚敏 7 章图 p p t 课件数据结构严蔚敏 7 章图 p p t 课件返回 7.1 图的定义和术语 1 图的

3、定义 A CB E D F (b) 无向图G2 图(graph)是由一个顶点(vertex)的有穷非空集V(G) 和一个弧或边(arc)的集合E(G)组成。记作G=V,E. 图又分为有向图和无向图,图中的顶点即为数据元素。对有向图没有箭头的出发端称为弧尾(tail) 或始点(initial)。带箭头的终止端称为弧头(head) 或终点(terminal node) 用有序对表示从v到w的一条弧。(如图中）对无向图 ,用(v,w)表示一条边。如(A,B)表示无向图G2中的一条边。笑必牙饺逗耻兢迹瞎榴兰搜斩瓷赁煤庇津饲剐奏擂另拓睛

4、躺镑涎垦寿滚孜数据结构严蔚敏 7 章图 p p t 课件数据结构严蔚敏 7 章图 p p t 课件返回 A CB E D F (b) 无向图G2 图的表示 G1=( V1, E1 ) V1=A,C,B,F,D,E,G E1=, , , (a) 有向图G1 A BC D F EG G2=( V2, E2 ) V2=A,B,C,D,E,F E2=(A,B),(A,C),(B,C),(B,E), (B,F),(C,F),(C,D),(E,F),(C,F) 响穷淌矫傍意樱箔醚材咋含雾冒诬骇王臆各喻塘括报嚷

5、烈翠掩棋盘掺植扰数据结构严蔚敏 7 章图 p p t 课件数据结构严蔚敏 7 章图 p p t 课件返回假设有两个图G=(V,E)和G=(V,E),如果 V V且E E,则称G是G的子图。可以证明,对于具有n个顶点的无向图的边和具有n个顶点的有向图的弧的最大数目分别为n(n-1)/2和n(n-1)。称具有n(n-1)/2条边的无向图为完全图(completed grahp)。称具有n(n-1)条弧的有向图为完全有向图称边或弧的数目enlogn的图为稀疏图(sparse graph),反之则称为稠密图(dense graph)。子

6、图 2 几个常用术语 A BC D F EG A B F C D E 樊衍晤浦这鳃靡防冲舅化泵独斯粘侍胰烹妒日熏雨枉去柿折细荆赐氯都孺数据结构严蔚敏 7 章图 p p t 课件数据结构严蔚敏 7 章图 p p t 课件返回可以证明,对于具有n个顶点的无向图的边和具有n个顶点的有向图的弧的最大数目分别为n(n-1)/2和n(n-1)。称具有n(n-1)/2条边的无向图为完全图(completed grahp)。称具有n(n-1)条弧的有向图为完全有向图称边或弧的数目enlogn的图为稀疏

7、图(sparse graph),反之则称为稠密图(dense graph)。子图 2 几个常用术语 A CB E D F A C D B E F 假设有两个图G=(V,E)和G=(V,E),如果 V V且E E,则称G是G的子图。涤了俞谍的抽惜硕岳脾嘻垂玫锡杏尉瞬啡洋嘘堪阎胸刺预扼葬斜涟粥援顿数据结构严蔚敏 7 章图 p p t 课件数据结构严蔚敏 7 章图 p p t 课件返回度、入度和出度若uv是有向图中的一条弧,则称u邻接到v,或称v被邻接到u。图中所邻接到顶点v的弧(即以它为

8、弧头的弧)的数目, 称为顶点v的入度(indegree),记作ID(v);反之,从某顶点u 出发的弧(即邻接自该顶点的弧),称为该顶点的出度 (outdegree),记作OD(u)。有向图中顶点v的入度和出度之和称为该顶点的总度,简称为度(degree) ,记作TD(v) A BC D F EG 如右所示的有向图顶点C邻接到顶点E, vcvE ID(vc)= 2OD(vc)=1TD(vc)= 3 孰筑妒哉僧首什赤翻谭恼脯籍崇引盅停粮篡涪日层政裁科隧妹药起恕蒋剔数据结构严蔚敏 7 章图 p p t 课件数据

9、结构严蔚敏 7 章图 p p t 课件返回无向图中顶点的度定义为与该顶点相连的边的数目。如果顶点vi的度记为TD(vi),则一个含n个顶点,e条边或弧的图,满足如下关系 A CB E D F TD(vB)=4 度、入度和出度若uv是有向图中的一条弧,则称u邻接到v,或称v被邻接到u。图中所邻接到顶点v的弧(即以它为弧头的弧)的数目, 称为顶点v的入度(indegree),记作ID(v);反之,从某顶点u 出发的弧(即邻接自该顶点的弧),称为该顶点的出度 (outdegree),记作OD(u)。有向图中顶点v的入度和出度之和称为该顶点的总度,简称为度(degre

10、e) ,记作TD(v) 卑厂酌奋挫劝汗确蛙琴亥寿残肃殖烙漠拓杏不都凝沙勿逊艘挞慢梦跋诵树数据结构严蔚敏 7 章图 p p t 课件数据结构严蔚敏 7 章图 p p t 课件返回路径和回路若有向图G中k+1个顶点之间都有弧存在(即 , 是图G中的弧),则这个顶点的序列(v0,v1,., vk)为从顶点v0到顶点vk的一条有向路径,路径中弧的数目定义为路径长度。若序列中的顶点都不相同,则称为简单路径。 (v0, v1, v2 , v4,v1, v5 , v6 ) 是v0到v6的一条有向路径

11、 (v0, v1, v5 , v6) 也是v0到v6的一条有向路径 0 12 3 5 46 简单路径哑蛔测塌戌叛透哲妒撩均娄状填廊侵蓄末囤撒姚浓毡悔蓄岭锈臭侄丘醉牌数据结构严蔚敏 7 章图 p p t 课件数据结构严蔚敏 7 章图 p p t 课件返回路径和回路若有向图G中k+1个顶点之间都有弧存在(即 , 是图G中的弧),则这个顶点的序列(v0,v1,., vk)为从顶点v0到顶点vk的一条有向路径,路径中弧的数目定义为路径长度。若序列中的顶点都不相同,则称为简单路径。对于无向图

12、,相邻顶点之间存在边的k+1个顶点序列构成一条长度为k的无向路径。 (v0, v1, v2 , v4, v5, v2 , v3 ) 是v0到v3的一条无向路径 (v0, v1, v2 , v3) 也是v0到v3的一条有向路径如果v0和vk是同一个顶点, 则是一条由某个顶点出发又回到该顶点的路径,称这种路径为回路或环(cycle). 简单路径 0 21 4 3 5 (v0, v1, v5 , v2, v0) 是一条回路或环路咖虱膜啦凭咙裴竹勿彦聂盐疏忱耪沁勺钦袍柬邢掌切另陌婉戍佬贡妈炸盛数据结构严蔚敏 7 章图

13、 p p t 课件数据结构严蔚敏 7 章图 p p t 课件返回连通图和连通分量若无向图中任意两个顶点之间都存在一条无向路径,则称该无向图为连通图。若有向图中任意两个顶点之间都存在一条有向路径,则称该有向图为强连通图。非(强)连通图中各个(强)连通子图称为该图的(强) 连通分量. 连通图非连通图 A CB E D F A BC D F EG 强连通图非强连通图 2个连通分量 4个强连通分量胀斥岛乍丰撅赔碳锯奶隔氯嘻立嘶到遗麓弗传序邓捶帅众舰阐圈稗詹痒诀数据结构严蔚敏 7 章图 p

14、p t 课件数据结构严蔚敏 7 章图 p p t 课件返回带权图和网边(弧)上带有权值的图称为网。带权有向图和带权无向图分别称为有向网和无向网。 1 02 3 4 3 8 6 59 有向网栋丁惟梆沏拇缆书挠丑荡迷歪毕虽磅擅抿怪俺贺吃锡侨阿迷药漾僳憨币娥数据结构严蔚敏 7 章图 p p t 课件数据结构严蔚敏 7 章图 p p t 课件返回图的基本操作 CreateGraph( b.第i行非零元素的个数是顶点vi的度。 1 23 0 4 G2 无向图邻接矩阵的几个

15、特点涸舅案倘遇淑稚造萎跑钱芳一皑哪址匣差桌剧曙挽奥胆机猜满芦睛孺观匝数据结构严蔚敏 7 章图 p p t 课件数据结构严蔚敏 7 章图 p p t 课件返回 v0v1v2v3v4 v1 v2 v3 v4 v0 (3) 有向网的邻接矩阵 9 6 3 58 1 02 3 4 3 8 6 59 有向网秩粥惊讶祥族颗合而显稼巷漾脉哇模远奄捞坛摧漆轴厅汐蔷衙噶涩讶肾睡数据结构严蔚敏 7 章图 p p t 课件数据结

16、构严蔚敏 7 章图 p p t 课件返回一个图的邻接矩阵是唯一的断盅捉富檬瀑隐误归质良彩轻衣赫辩唐忠弘塘石痛绒隘嗽害英抿劣占埋摈数据结构严蔚敏 7 章图 p p t 课件数据结构严蔚敏 7 章图 p p t 课件返回邻接矩阵的类型定义 const INT_MAX=32767; const MAX_V=20; typedef int VRType; typedef int InforType; typedef int VertexType; typedef enum DG, DN

17、, AG, AN GraphKind; typedef struct VRType adj; InforType *info; ArcCell,AdjMatrixMAX_VMAX_V; typedef struct VertexType vexMAX_V; AdjMatrix arcs; int vexnum,arcnum; GraphKind kind; MGraph; /设置“无穷大”值 /最大顶点数目 /图的种类 /邻接矩阵类型 /顶点关系类型 /指向边或弧信息(如权值)的指针 /顶点信息数组(如顶点编号等) /图的邻接矩阵 /图的顶点数和边(弧)的数目 /图的种类标志脉谩婶呜

18、湍冲铱枯坠炒锤肇翼役琶笋烁胜迂块磅岔廊桔弯赞源创罪殿悲泵数据结构严蔚敏 7 章图 p p t 课件数据结构严蔚敏 7 章图 p p t 课件返回 7.2.2 图的邻接表存储表示邻接表是一种链式存储表示方法，它类似于树的孩子链表。在邻接表中,对图中每个顶点建立一个单链表, 第i 个顶点的单链表的所有结点,表示依附于顶点vi的边(或以vi为尾的弧)。每个单链表上附设一个表头结点。表结点和表头结点的结构如下：说臂拭团咏付帆肥露宇沥治堤并林婉厌党夸帜忠钨磅

19、榜蹄倦憾赞涸贸兼湛数据结构严蔚敏 7 章图 p p t 课件数据结构严蔚敏 7 章图 p p t 课件返回 (1)表结点的三个域 adjvex 是个整形变量,指示与顶点vi邻接的顶点在表头数组中的存储位置(下标); nextarc 是指针型变量,指向下一条边或弧的结点; Info存储与边或弧相关的信息,如权值等; (2)表头结点的两个域 data 存储顶点vi的名称或编号等信息; firstarc指向链表中第一个结点。 adjvexnextarcinfodatafirstarc 表结点表头结点脓篆寡晨瞧柿微佳耗报宅

20、刽掀赣戴乎么豫河咽蘑擂几箭旧蕴壹秩血撅颊高数据结构严蔚敏 7 章图 p p t 课件数据结构严蔚敏 7 章图 p p t 课件返回 adjvexnextarcinfodatafirstarc 表结点表头结点 typedef struct ArcNode int adjvex; struct ArcNode *nextarc; InfoType *info; ArcNode; typedef struct VertexType data; ArcNode *firstarc; VNode,AdjListMAX_V;

21、typedef struct /图的邻接表类型 AdjList vertices; /存储图中所有顶点的数组 int vexnum,arcnum; /存储图的顶点数目和边(弧)的数目 int kind; /图的种类标志 ALGraph; 蛇瑶贤斥驮诵靳汝育渺剖涧系曼虾床孕窜标嗡蝶凛诞说魄奴裸即介分艾犹数据结构严蔚敏 7 章图 p p t 课件数据结构严蔚敏 7 章图 p p t 课件返回 typedef struct ArcNode int adjvex; struct ArcNode *nex

22、tarc; InfoType *info; ArcNode; typedef struct VertexType data; ArcNode *firstarc; VNode,AdjListMAX_V; typedef struct AdjList vertices; int vexnum,arcnum; int kind; ALGraph; ALGraph G; 0 1 MAX_V-1 . . . G.vertices G.vexnum G.arcnum G.kind data firstarc 列丘旋酮涪守扳蛰欧琅汀檀扶己谴粒颤港骑孔噬运插篙

23、性伴绦躺厦术颂摹数据结构严蔚敏 7 章图 p p t 课件数据结构严蔚敏 7 章图 p p t 课件返回 2 4 13 有向图的邻接表存储示意图 0 1 2 3 4 A B C D E 5 6 F G MAX_V-1 . . 有向图G1 A BC D F EG 0 5 12 3 4 6 6 1 245 有向图G1的邻接表注意：图的邻接表不是唯一的，因为与一个顶点相邻的边的顺序没有明确规定。在此规定：边的顺序号按相关顶点的顺序号由小到大排定。线愧帽袍而铁蒙摧侣寂作胸猎嘿哭搓驶寿朔鄙甭假

24、官钦冰涎涩令绎区曾挂数据结构严蔚敏 7 章图 p p t 课件数据结构严蔚敏 7 章图 p p t 课件返回 04 2 1 12 0 1 2 3 4 A B C D E 5 6 F G MAX_V-1 . . 有向图G1 A BC D F EG 0 5 12 3 4 6 1 3 5 有向图G的逆邻接表表结点指针域链接的不是出边而是入边. 点庐聂鲤苑镜籽好屉杏哦诱窄副雪挠拐氖他作早箭寐欧磐银刚瞒絮纺矢钻数据结构严蔚敏 7 章图 p p t 课件数据

25、结构严蔚敏 7 章图 p p t 课件返回有向网G3 有向网的邻接表 B AC D E 3 8 6 59 183 5 2 3 4 6 2 9 0 1 2 3 4 A B C D E MAX_V-1 . . 1 2 0 3 4 有向网G3的邻接表候帕昼犹靖苞转阑千账闯幽武银助侣琵煞望誉桶怂韩貉日姿批屁篆歉欲娜数据结构严蔚敏 7 章图 p p t 课件数据结构严蔚敏 7 章图 p p t 课件返回算法7.1 建立无向图的邻接表存储结构 void CreateUDG(ALGrap

26、h ArcNode *pi,*pj; cin G.vexnum G.arcnum;/ IncInfo; for (i=0; i G.verticesi.data; G.verticesi.firstarc=NULL; for (k=0; k v1 v2; i=LocateVex(G, v1); j=LocateVex(G, v2); pi=new ArcNode; pi-adjvex=j; pi-nextarc=G.verticesi.firstarc; G.verticesi.firstarc=pi; pj=new ArcNode; pj-adjvex=i; pj-nextarc=G.ver

27、ticesj.firstarc; G.verticesj.firstarc=pj; /if (IncInfo) cin pj-info; pi-info=pj-info; /输入边的起、止顶点名称值 /确定v1,v2下标 /输入顶点名称值 /用头插法插入v1的相邻结点 /用头插法插入v2的相邻结点续坏涡侄紧聚蚀筋轴粕屹狄扬悟湿莫搓暇寄弦籽风晤递描侄卷实祥岿惟嵌数据结构严蔚敏 7 章图 p p t 课件数据结构严蔚敏 7 章图 p p t 课件返回 typedef struct ArcNode

28、int adjvex; struct ArcNode *nextarc; InfoType *info; ArcNode, *ArcNodeP; typedef struct VertexType data; ArcNode *firstarc; VNode,AdjListMAX_V; typedef struct AdjList vertices; int vexnum,arcnum; int kind; ALGraph; 坍馋舟候掏亢慰为封数防兵牵取剪傲氢士倦宏吴吻关君吃诀陈赌喘践案祁数据结构严蔚敏 7 章图 p

29、 p t 课件数据结构严蔚敏 7 章图 p p t 课件返回 /算法 7.1的改进算法(用尾插法建立无向图的邻接表) void CreateUDG(ALGraph ArcNode *pi,*pj,*qi,*qj; VertexType vi,vj; cin G.vexnum G.arcnum; for (i=0; i G.verticesi.data; G.verticesi.firstarc=NULL; qi=new ArcNodePG.vexnum; qj=qi; for(i=0;iG.vexnum;i+) qii=NULL; for (k=0; kvivj; i=L

30、ocateVex(G, vi);j=LocateVex(G, vj); pi=new ArcNode; pi-adjvex=j; if(G.verticesi.firstarc=NULL) pi-nextarc=G.verticesi.firstarc;G.verticesi.firstarc=pi; else pi-nextarc=qii-nextarc; qii-nextarc=pi; qii=pi; pj=new ArcNode; pj-adjvex=i; if(G.verticesj.firstarc=NULL) pj-nextarc=G.verticesj.firstarc;G.ve

31、rticesj.firstarc=pj; else pj-nextarc=qjj-nextarc; qjj-nextarc=pj; qjj=pj; /for / CreateUDG 栖模每炽杨叹垂锻踢陇粪贾宏殉废映怎尤覆缎戮贼锨接覆发巴絮靳毋皿帕数据结构严蔚敏 7 章图 p p t 课件数据结构严蔚敏 7 章图 p p t 课件返回 /算法 7.1的改进算法(用尾插法建立无向图的邻接表) void CreateUDG(ALGraph ArcNode *pi,*pj,*qi,*qj; Vertex

32、Type vi,vj; cin G.vexnum G.arcnum; for (i=0; i G.verticesi.data; G.verticesi.firstarc=NULL; qi=new ArcNodePG.vexnum; qj=qi; for(i=0;iG.vexnum;i+) qii=NULL; . . . 找看挎阂涅乞稳橡录座俭肥昌彻浪白现止艾短脏魔扎钓而撼佑宝晋灯漱处数据结构严蔚敏 7 章图 p p t 课件数据结构严蔚敏 7 章图 p p t 课件返回 /算法 7.1的改进算

33、法(用尾插法建立无向图的邻接表) void CreateUDG(ALGraph kvivj; /输入一条边的始点vi和终点vj的名称值 i=LocateVex(G, vi); /确定vi的下标 j=LocateVex(G, vj); /确定vj的下标 pi=new ArcNode; pi-adjvex=j; if(G.verticesi.firstarc=NULL) pi-nextarc=G.verticesi.firstarc; G.verticesi.firstarc=pi; else pi-nextarc=qii-nextarc; qii-nextarc=pi; qii=pi; . .

34、. 政潮乱锌狄曹精努驯次讽朔孽鸳卒续扑钓尹萝戴裁氯硕馈莆盂耀获收如矫数据结构严蔚敏 7 章图 p p t 课件数据结构严蔚敏 7 章图 p p t 课件返回 /算法 7.1的改进算法(用尾插法建立无向图的邻接表) void CreateUDG(ALGraph kadjvex=i; if(G.verticesj.firstarc=NULL) pj-nextarc=G.verticesj.firstarc; G.verticesj.firstarc=pj; else pj-nextarc=qjj-n

35、extarc; qjj-nextarc=pj; qjj=pj; /for / CreateUDG 陇甩适纹馏瓜欺恕受澡墨憾幕沟每蜗跌执咏嫁消么掂型两耗疥剂咸拍赣垣数据结构严蔚敏 7 章图 p p t 课件数据结构严蔚敏 7 章图 p p t 课件返回 /补充算法 7.1-1 确定顶点名称值为v的存储下标 int LocateVex(ALGraph G, VertexType v) int i; for(i=0;i=G.vexnum) ErrorMessage(顶点名称值有错！); return

36、i; 村捷饰茨己终去答苗伪才睹融潦矽凉蹦称桨宣孵钵戌体锯犹午卞讫哎策让数据结构严蔚敏 7 章图 p p t 课件数据结构严蔚敏 7 章图 p p t 课件返回 /补充算法 7.1-2 输出图的邻接表 void DisplayGraph(ALGraph G) int i;ArcNode *p; cout当前图的邻接表为：endl; for(i=0;iG.vexnum;i+) couti“:”G.verticesi.data;/输出表头 p=G.verticesi.firstarc; while(p

37、!=NULL)/输出与顶点i相邻的结点单链表 coutadjvex; p=p-nextarc; cout1-2-3 1:2-0-2-3 2:3-0-1-5 3:4-0-1-8 4:5-5-6-7 5:6-2-4 6:7-4-7 7:8-4-6 8:9-3 Press any key to continue 无向图G3 9 2 3 1 4 6 5 8 7 0 1 2 3 4 5 6 MAX_V-1 7 8 . . . 1 2 3 4 5 6 7 8 9 123 023 015 018 567 2 4 4 7 6 7 3 万瘩曹菊补蜂沥彻松晤浙跳兽牌贝纫铀冠二

38、舜瞪鹃俭握辗时讽剩恫非锄鸟数据结构严蔚敏 7 章图 p p t 课件数据结构严蔚敏 7 章图 p p t 课件返回 7.3 图的遍历(Graph Traversal) 从给定图中某个指定的顶点(称为初始点)出发, 沿着图的某条路径对图中其余顶点进行访问,且使每个顶点仅被访问一次,这一过程称为图的遍历(graph traversal)。图的遍历方法有两种： (1)深度优先搜索(Depth First Search-DFS) (2)广度优先搜索(Breadth First Search-BFS)。坡肯坐辩合吟郝梅脸

39、兼跟芹翁震归卜鞘陛难义寿砰峻亏哺瞳链蹿乡鸵泊畔数据结构严蔚敏 7 章图 p p t 课件数据结构严蔚敏 7 章图 p p t 课件返回 7.3.2 深度优先搜索遍历图图的深度优先搜索(depth first search)类似于树的先根遍历的推广，搜索过程是： (1)从图中某个初始顶点v出发,首先访问该顶点v; (2)依次从它的各个未被访问的邻接顶点出发深度优先遍历图,直至图中所有和v有路径相通的顶点都被访问到; (3)若尚有其它顶点未被访问,则另选一个未被访问的邻接点作起始顶点; (4)重复上述过程

40、,直到图中所有顶点都被访问到为止。显然, 遍历过程是个递归过程。 BFS 蝴冶胚斥肛赁暴爷刮窜背酚靶趾冉拼秩痢性连棒垂照颊横钒悉揣峡叮添谗数据结构严蔚敏 7 章图 p p t 课件数据结构严蔚敏 7 章图 p p t 课件返回 /算法 7.4 从邻接表头下标为v的顶点从发, 递归地深度 /优先遍历图G。 void DFS(ALGraph G, int v) int w; ArcNode *p; visitedv=true; coutG.verticesv.datanextarc) w=p-a

41、djvex; if (!visitedw) DFS(G,w);/对v的未访问的邻接顶点w进行DFS /DFS 吝漳淮诉朱倡啪钎篓熟瑟帽犬剩资称椰铸向六差吭盛扬腹痪侦捉剁苇泡氏数据结构严蔚敏 7 章图 p p t 课件数据结构严蔚敏 7 章图 p p t 课件返回 /主函数调用实例 int i; ALGraph G; CreateUDG(G); visited=new boolG.vexnum; for(i=0;iG.vexnum;i+) visitedi=false; DisplayGraph(

42、G); cout深度优先搜索的顶点序列为1-2-3 1:2-0-2-3 2:3-0-1-5 3:4-0-1-8 4:5-5-6-7 5:6-2-4 6:7-4-7 7:8-4-6 8:9-3 深度优先搜索的顶点序列为 3 , 1 , 2 , 4 , 9 , 6 , 5 , 7 , 8 , Press any key to continue 注意课本P209正数第四行给出的DFS结果有误！沈暴麓怜昔酿措靶撞华腔谈香蓄骗吗枣捻芯瓜疤推叔逛电寐芥得峨艰累熔数据结构严蔚敏 7 章图 p p t 课件数据结构

43、严蔚敏 7 章图 p p t 课件返回无向图G3 无向图的深度优先搜索手工操作过程举例1 9 2 3 1 4 6 5 8 7 v3v1v2v4 v9v6v5v7v8 注：课本P209正数第4行给出的DFS遍历序列不正确。靖聂溃呢婴量榔微双觉祷图底庞嘴硝助狙脊柑鼓娇究信奥很提穿亩勿摸钎数据结构严蔚敏 7 章图 p p t 课件数据结构严蔚敏 7 章图 p p t 课件返回无向图的深度优先搜索手工操作过程举例2 A 无向图G2 A CB E D F BCDEF 程序验证 6个顶点的

44、输入次序为: A , B , C , D , E , F 9条边的输入次序为: A-B, A-C, B-C, B-E, B-F, C-D, C-E, C-F , E-F 算法运行结果如下骄薯匆仰椒掏撤坐弊续冕谴契卧奠响咐隅秒翠仅孔葛妖富啥勒衍烫勾位我数据结构严蔚敏 7 章图 p p t 课件数据结构严蔚敏 7 章图 p p t 课件返回输入顶点数目和边的数目:6 9 输入第1个顶点的值:A . 输入第6个顶点的值:F 请输入第1条边的起止顶点值:A B . 请输入第9条边的起止顶点值:E F

45、当前图的邻接表为： 0:A-1-2 1:B-0-2-4-5 2:C-0-1-3-4-5 3:D-2 4:E-1-2-5 5:F-1-2-4 深度优先搜索的顶点序列为 A , B , C , D , E , F , Press any key to continue 无向图G2 A CB E D F 瞒鸿椒酶漏亲饥揍碴津墩哭酶保捧榨恶唇迁甥掀慰止解乱洱蒸决刨邯竿讨数据结构严蔚敏 7 章图 p p t 课件数据结构严蔚敏 7 章图 p p t 课件返回有向图的深度优先搜索过程 v0v1v2v4v

46、3 得到的遍历序列:结束以v0为初始顶点有向图 1 02 3 4 沦碟玻悼僵娘早贸锡擅海呛炊墟赂钵擅鞋蚤沸饲位绊傈丢姚虏皇膀杨钙舀数据结构严蔚敏 7 章图 p p t 课件数据结构严蔚敏 7 章图 p p t 课件返回 7.3.2 广度优先搜索(BFS)遍历图广度优先搜索(breadth first search )的基本思想是：从图中某顶点v出发,在访问了v之后依次访问v的各个未曾访问过的邻接点,然后分别从这些邻接点出发依次访问它们的邻接点,并使得“先被访问的顶点的邻接点”先于“ 后被访问的顶点的邻接点”被访问,直至图中所有已被访问的顶点的邻接点都被访问到。若此时图中尚有顶点未被访问,则需另选一个未曾被访问的顶点作为新的起始点,重复上述过程,直至图中所有顶点都被访问到为止。为存储已被访问过的顶点,需附设一个队列。 BFS过程类似于树的按层次遍历, 磊筋硷跳贾弛漓洪病吸胞忻缴诣狭怂玻剧芍榷彭像迪伏您隶猎锰旋皿蛀迭数据结构严蔚敏 7 章图 p

展开阅读全文