《数据结构教学课件第7章》由会员分享，可在线阅读，更多相关《数据结构教学课件第7章（68页珍藏版）》请在金锄头文库上搜索。
1、1数据结构疲舜翔澡篮窟往溉瞪掷夸辟郧匝陋母沈滩橙血虞掏阿蝇飞荣咬孙专荒哑唤数据结构教学课件第7章数据结构教学课件第7章27.1 7.1 基本术语基本术语7.2 7.2 存储结构存储结构7.3 7.3 图的遍历图的遍历7.4 7.4 图的其他运算图的其他运算7.5 7.5 图的应用图的应用第第7 7章章 图图铜榜涪藉求络爸酋碾讥明孔肤羹低何厩腕挨员丑褒萨亚门谣撤蓄蜕士辛全数据结构教学课件第7章数据结构教学课件第7章37.1 7.1 图的基本术语图的基本术语图：图：记为记为 G( V, E ) 其中：其中：V 是是G的顶点集合，是有穷非空集；的顶点集合，是有穷非空集； E 是是G的边的边集合，是有
2、穷集。集合，是有穷集。问：当问：当E(G)E(G)为空时，图为空时，图G G存在否？存在否？答：还存在！但此时图答：还存在！但此时图G G只有顶点而没有边。只有顶点而没有边。有向图：有向图：无向图：无向图：完全图：完全图：图图G G中的每条边都是有方向的；中的每条边都是有方向的；图图G G中的每条边都是无方向的；中的每条边都是无方向的；图图G G任意两个顶点都有一条边相连接；任意两个顶点都有一条边相连接；vv若若若若 n n 个顶点的无向图有个顶点的无向图有个顶点的无向图有个顶点的无向图有 n n( (n n-1)/2 -1)/2 条边条边条边条边, , 称为称为称为称为无向完全图无向完全图无
3、向完全图无向完全图vv若若若若 n n 个顶点的有向图有个顶点的有向图有个顶点的有向图有个顶点的有向图有n n( (n-n-1) 1) 条边条边条边条边, , 称为称为称为称为有向完全图有向完全图有向完全图有向完全图V=vertex E=edge赛抠彦油赢舟郧趾搽逆瘸凯酋抵孔剧祸拒哦畦媚而徊绽屡海疡萌歉谤强辰数据结构教学课件第7章数据结构教学课件第7章4证明： 完全有向图有完全有向图有完全有向图有完全有向图有n n( (n n-1)-1)条边条边条边条边。证明：若是完全有向图，则顶点证明：若是完全有向图，则顶点证明：若是完全有向图，则顶点证明：若是完全有向图，则顶点1 1必必与所有其他顶点各有
4、必必与所有其他顶点各有必必与所有其他顶点各有必必与所有其他顶点各有2 2条条条条连线，即有连线，即有连线，即有连线，即有2(n-1)2(n-1)条边，条边，条边，条边， 顶点顶点顶点顶点2 2有有有有2(n-2)2(n-2)条边，条边，条边，条边，顶点，顶点，顶点，顶点n-1n-1有有有有2 2条边条边条边条边, ,顶点顶点顶点顶点n n有有有有0 0条边条边条边条边. .总边数总边数总边数总边数2( n-12( n-1 n-2 n-21 10)=2(n-1+0)n/2= 0)=2(n-1+0)n/2= n n( (n n-1)-1)完全无向图有完全无向图有完全无向图有完全无向图有n n( (
5、n n-1)/2 -1)/2 条边条边条边条边。证明：若是完全无向图，则顶点证明：若是完全无向图，则顶点证明：若是完全无向图，则顶点证明：若是完全无向图，则顶点1 1必与所有其他顶点各有必与所有其他顶点各有必与所有其他顶点各有必与所有其他顶点各有1 1条连条连条连条连线，即有线，即有线，即有线，即有n-1n-1条边，顶点条边，顶点条边，顶点条边，顶点2 2有有有有n-2n-2条边，条边，条边，条边，顶点，顶点，顶点，顶点n-1n-1有有有有1 1条边条边条边条边, ,顶顶顶顶点点点点n n有有有有0 0条边条边条边条边. .总边数总边数总边数总边数 n-1 n-1 n-2 n-21 10=0=
6、（n-1+0)n/2= n-1+0)n/2= n n( (n n-1)/2 -1)/2 铣浸崩田哥悍碧亚朱逮祭匀砾布港侗获旦银划噬烯裙揩蕾株俯咨击仟簧荣数据结构教学课件第7章数据结构教学课件第7章5例：例：判断下列判断下列4种图形各属什么类型？种图形各属什么类型？无向无向无向图无向图(树树)有向图有向图有向有向n n( (n n-1)/2 -1)/2 条边条边条边条边n n( (n n-1) -1) 条边条边条边条边G1G1的顶点集合为的顶点集合为V(G1)V(G1)=0,1,2,3=0,1,2,3边集合为边集合为E(G1)E(G1)=(0,1),(0,2),(0,3),(1,2),(1,3)
7、,(2,3)=(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)完全图完全图完全图完全图屁毡艰皮柠紧棚携迄榆逝殖裔续匠曳谐囊汲限冰汗为允词爬琵毡电架折丝数据结构教学课件第7章数据结构教学课件第7章6稀疏图：稠密图： 设有两个图设有两个图 G(V, E) 和和 G(V, E)。若。若 V V 且且 E E, 则称则称 图图G 是是 图图G 的子图。的子图。子 图：边较少的图。通常边数边较少的图。通常边数n2边很多的图。无向图中，边数接近边很多的图。无向图中，边数接近n n( (n n-1)/2 -1)/2 ； 有向图中，边数接近有向图中，边数接近n n( (n n-1) -1
8、) 畅怖技崖刀卿粹灵蚊仰室孙豪空盈倘胡多白错潜肪慷采加易祥手糠除雍漫数据结构教学课件第7章数据结构教学课件第7章7带权图：带权图：即边上带权的图。其中即边上带权的图。其中权权是指每条边可以标上是指每条边可以标上具有某种含义的数值（即与边相关的数）。具有某种含义的数值（即与边相关的数）。连通图：连通图：在在在在无向无向无向无向图中图中图中图中, , 若从顶点若从顶点若从顶点若从顶点v v1 1到顶点到顶点到顶点到顶点v v2 2有路径有路径有路径有路径, , 则称顶点则称顶点则称顶点则称顶点v v1 1与与与与v v2 2是是是是连通连通连通连通的。如果图中任意一对顶点都是连通的的。如果图中任意
9、一对顶点都是连通的的。如果图中任意一对顶点都是连通的的。如果图中任意一对顶点都是连通的, , 则称此图是则称此图是则称此图是则称此图是连通图连通图连通图连通图。非连通图的极大连通子图非连通图的极大连通子图非连通图的极大连通子图非连通图的极大连通子图叫做叫做叫做叫做连通分量连通分量连通分量连通分量。带权图带权图网网 络：络：陌卤盆统耿嘉侥立畸孤滑赏回宏卯钥坛隙昔诱线介卤耿笑跳鲍似琵愈名酞数据结构教学课件第7章数据结构教学课件第7章8在在在在有向有向有向有向图中图中图中图中, , 若对于每一对顶点若对于每一对顶点若对于每一对顶点若对于每一对顶点v vi i和和和和v vj j, , 都存在一都存在
10、一都存在一都存在一条从条从条从条从v vi i到到到到v vj j和和和和从从从从v vj j到到到到v vi i的路径的路径的路径的路径, , 则称此图是则称此图是则称此图是则称此图是强连通图强连通图强连通图强连通图。 非强连通图的极大强连通子图非强连通图的极大强连通子图非强连通图的极大强连通子图非强连通图的极大强连通子图叫做叫做叫做叫做强连通分量强连通分量强连通分量强连通分量。强连通图：强连通图：有两类图形有两类图形不在本章讨不在本章讨论之列：论之列：待袭谴号侧栖橡矮靖浊笼回呐岁谤差址释卡霖芯衣纽肉珠欠坠尸瞬沙耐楷数据结构教学课件第7章数据结构教学课件第7章9邻接点：有向边有向边(u, v
11、)称为弧，边的始点称为弧，边的始点u叫叫弧尾弧尾，终点，终点v叫叫弧弧头头 顶点顶点v的度的度是与它相关联的边的条数。记作是与它相关联的边的条数。记作TD(v)。 在在有向图有向图中中, 顶点的度等于该顶点的顶点的度等于该顶点的入度入度与与出度出度之和。之和。 顶点顶点 v 的入度的入度是以是以 v 为终点的有向边的条数为终点的有向边的条数, 记作记作 ID(v); 顶点顶点 v 的出度的出度是以是以 v 为始点的有向边的条数为始点的有向边的条数, 记作记作 OD(v)。若若 (u, v) 是是 E(G) 中的一条边，则称中的一条边，则称 u 与与 v 互为互为邻接顶点邻接顶点弧头和弧尾：度、
12、入度和出度：如嗽酚袒信全带彩牺卸斤厌普洗练擦真碗咖纳本镭收拌荡酪石祥轧舟窝易数据结构教学课件第7章数据结构教学课件第7章10生成树：生成树：是一个是一个是一个是一个极小连通子图极小连通子图极小连通子图极小连通子图，它含有图中全部顶点，但只有，它含有图中全部顶点，但只有，它含有图中全部顶点，但只有，它含有图中全部顶点，但只有n n- -1 1条边条边条边条边。vv如果在生成树上添加如果在生成树上添加如果在生成树上添加如果在生成树上添加1 1条边，必定构成一个环。条边，必定构成一个环。条边，必定构成一个环。条边，必定构成一个环。vv若图中有若图中有若图中有若图中有n n个顶点，却少于个顶点，却少于
13、个顶点，却少于个顶点，却少于n n-1-1条边，必为非连通图。条边，必为非连通图。条边，必为非连通图。条边，必为非连通图。生成森林：生成森林：问：问：当有向图中仅当有向图中仅1 1个顶点的入度为个顶点的入度为0,0,其余顶点的其余顶点的入度均为入度均为1 1，此时是何形状？，此时是何形状？由若干棵生成树组成，含全部顶点，但构成这些由若干棵生成树组成，含全部顶点，但构成这些由若干棵生成树组成，含全部顶点，但构成这些由若干棵生成树组成，含全部顶点，但构成这些树的边是最少的。树的边是最少的。树的边是最少的。树的边是最少的。答：答：是树！而且是一棵有向树！是树！而且是一棵有向树！己纺饭测媚筏婪雹泞扯杏
14、碎贮优臭室嘛耗聚球典不宙距蛀茬鳞侮乔来酷茸数据结构教学课件第7章数据结构教学课件第7章11路径：在图在图在图在图 G G( (V V, , E E) ) 中中中中, , 若从顶点若从顶点若从顶点若从顶点 v vi i 出发出发出发出发, , 沿一些边沿一些边沿一些边沿一些边经过一些顶点经过一些顶点经过一些顶点经过一些顶点 v vp p1 1, , v vp p2 2, , , v vpmpm，到达顶点，到达顶点，到达顶点，到达顶点v vj j。则。则。则。则称顶点序列称顶点序列称顶点序列称顶点序列 ( ( v vi i v vp p1 1 v vp p2 2 . . v vpm pm v vj
15、 j ) ) 为从顶点为从顶点为从顶点为从顶点v vi i 到顶到顶到顶到顶点点点点 v vj j 的的的的路径路径路径路径。它经过的边。它经过的边。它经过的边。它经过的边( (v vi i, , v vp p1 1) )、( (v vp p1 1, , v vp p2 2) )、. .、( (v vpmpm, , v vj j) )应当是属于应当是属于应当是属于应当是属于E E的边。的边。的边。的边。路径长度：非带权图的路径长度是指此路径上非带权图的路径长度是指此路径上非带权图的路径长度是指此路径上非带权图的路径长度是指此路径上边的条数边的条数边的条数边的条数；带权图的路径长度是指路径上带权
16、图的路径长度是指路径上带权图的路径长度是指路径上带权图的路径长度是指路径上各边的权之和各边的权之和各边的权之和各边的权之和。剔亲洲慎链畅闷械却廉绪筹参消该盟赐蔷蛾探集级培疾瘸潜禾侮奇奈裔抬数据结构教学课件第7章数据结构教学课件第7章12简单路径：路径上各顶点路径上各顶点 v v1 1,v,v2 2,.,v,.,vm m 均不互相重复。均不互相重复。回 路：例：例：若路径上第一个顶点若路径上第一个顶点 v v1 1 与最后一个顶点与最后一个顶点v vm m 重合，重合，则称这样的路径为则称这样的路径为回路或环回路或环。洼症形拆默堰锐计坟劲辖忿天稳欢淋练聂碳粳垫虱瑟躲联缓解簧辆饥洼苹数据结构教学课
17、件第7章数据结构教学课件第7章137.2 7.2 图的存储结构图的存储结构图的特点：非线性结构（图的特点：非线性结构（m :n m :n ）邻接表邻接表邻接多重表邻接多重表十字链表十字链表设计为邻接矩设计为邻接矩阵阵链式存储结构：链式存储结构：顺序存储结构：顺序存储结构： 无！无！（多个顶点，无序可言）（多个顶点，无序可言）但可但可用用数组数组数组数组描述元素间关系。描述元素间关系。可用多重链表可用多重链表重点介绍：重点介绍：邻接矩阵邻接矩阵( (数组数组) )表示法表示法邻接表邻接表( (链式链式) )表示法表示法顺姑厩挑苟婴骚百丧妆寨肩吱屡桌课菲潦译剑壳勃懈厦烩酷誓驹游阑志泽数据结构教学课
18、件第7章数据结构教学课件第7章14一、邻接矩阵（数组）表示法一、邻接矩阵（数组）表示法一、邻接矩阵（数组）表示法一、邻接矩阵（数组）表示法vv建立一个建立一个建立一个建立一个顶点表顶点表顶点表顶点表（记录各个顶点信息）（记录各个顶点信息）（记录各个顶点信息）（记录各个顶点信息）和一个和一个和一个和一个邻接矩阵邻接矩阵邻接矩阵邻接矩阵（表（表（表（表示各个顶点之间关系）示各个顶点之间关系）示各个顶点之间关系）示各个顶点之间关系）。vv设图设图设图设图 A = ( A = (V V, , E E) ) 有有有有 n n 个顶点，则图的邻接矩阵是一个二维数个顶点，则图的邻接矩阵是一个二维数个顶点，则
19、图的邻接矩阵是一个二维数个顶点，则图的邻接矩阵是一个二维数组组组组 A A.Edge.Edge n n n n ，定义为：，定义为：，定义为：，定义为：v1v2v3v5v4v4A例例例例1 1：邻接矩阵：A.Edge =（ v1 v2 v3 v4 v5 ）v1v2v3v4v50 0 0 0 00 0 0 0 00 0 0 0 00 0 0 0 00 0 0 0 0分析分析分析分析1 1：无向图的邻接矩阵是无向图的邻接矩阵是无向图的邻接矩阵是无向图的邻接矩阵是对称对称对称对称的；的；的；的；分析分析分析分析2 2：顶点顶点顶点顶点i i 的的的的度度度度第第第第 i i 行行行行 ( (列列列列
20、) ) 中中中中1 1 的个数；的个数；的个数；的个数；特别：特别：特别：特别：完全图完全图完全图完全图的邻接矩阵中，对角元素为的邻接矩阵中，对角元素为的邻接矩阵中，对角元素为的邻接矩阵中，对角元素为0 0，其余全，其余全，其余全，其余全1 1。0 1 0 1 01 0 1 0 10 1 0 1 11 0 1 0 10 1 1 1 00 1 0 1 01 0 1 0 10 1 0 1 11 0 1 0 10 1 1 1 0顶点表：哑叶勺宛他涎闯浙花郴奏徐濒婆咖波谋浩空弯忠走蕊玲陪罪冠荧铅疯傲密数据结构教学课件第7章数据结构教学课件第7章15例例2 ：有向图的邻接矩阵有向图的邻接矩阵分析分析分析
21、分析1 1 1 1：有向图的邻接矩阵有向图的邻接矩阵可能是不对称可能是不对称的。的。分析分析分析分析2 2 2 2：顶点的顶点的出度出度= =第第i i行元素之和行元素之和，OD( Vi )= A.Edge i j 顶点的顶点的入度入度= =第第i i列元素之和列元素之和。ID( Vi )= A.Edge j i 顶点的顶点的度度= =第第i i行元素之和行元素之和+ +第第i i列元素之和列元素之和, , 即：即：TD(Vi)=OD( Vi ) + ID( Vi )v1v2v3v4A A邻接矩阵：A.Edge =( v1 v2 v3 v4 )v1v2v3v40 0 0 00 0 0 0 0
22、0 0 0 0 0 0 0 注：注：在有向图的邻接矩阵中，在有向图的邻接矩阵中， 第第i i行含义：以结点行含义：以结点v vi i为尾的弧为尾的弧( (即出度边）；即出度边）； 第第i i列含义：以结点列含义：以结点v vi i为头的弧为头的弧( (即入度边）。即入度边）。顶点表：0 1 1 00 0 0 0 0 0 0 1 1 0 0 0 0 1 1 00 0 0 0 0 0 0 1 1 0 0 0 逾镑杂间矫妓同傅硫亦脖音话牙军僳甭婿醒巍炕篷皇刻尹集渺其循设听矫数据结构教学课件第7章数据结构教学课件第7章16特别讨论特别讨论 ：网（即有权图）的邻接矩阵网（即有权图）的邻接矩阵定义为：定义
23、为： A.Edge i j =Wij 或（或（vi, vj）VR 无边（弧）无边（弧）v1v2v3v4Nv5v65489755613以有向网为例：以有向网为例：邻接矩阵： N.Edge =( v1 v2 v3 v4 v5 v6 )顶点表： 5 7 4 8 9 5 6 5 3 1 5 7 4 8 9 5 6 5 3 1 殊滥技亏仇浑伞丘厦闷试蹈烯册摇黄瞻焚薄墩桥草蔫筹澎卓您汰漂堑逛豹数据结构教学课件第7章数据结构教学课件第7章17 容易实现图的操作，如：求某顶点的度、判断容易实现图的操作，如：求某顶点的度、判断顶点之间是否有边（弧）、找顶点的邻接点等等。顶点之间是否有边（弧）、找顶点的邻接点等等
24、。 n n个顶点需要个顶点需要n*nn*n个单元存储边个单元存储边( (弧弧););空间效率空间效率为为O(nO(n2 2) )。 对稀疏图而言尤其浪费空间。对稀疏图而言尤其浪费空间。邻接矩阵法邻接矩阵法优点：优点：邻接矩阵法邻接矩阵法缺点：缺点：启彝玄嘘各泻梦亭胺掸谤育楼绑励津禁驰在坝按底凳嫂猎羹泣驰膀伴主净数据结构教学课件第7章数据结构教学课件第7章18二、邻接表（链式）表示法二、邻接表（链式）表示法二、邻接表（链式）表示法二、邻接表（链式）表示法vv对每个顶点对每个顶点对每个顶点对每个顶点v vi i 建立一个建立一个建立一个建立一个单链表单链表单链表单链表，把与，把与，把与，把与v v
25、i i有关联的有关联的有关联的有关联的边的信息边的信息边的信息边的信息（即（即（即（即度或出度边）度或出度边）度或出度边）度或出度边）链接链接链接链接起来，表中每个结点都设为起来，表中每个结点都设为起来，表中每个结点都设为起来，表中每个结点都设为3 3个域；个域；个域；个域；vv每个单链表还应当附设一个每个单链表还应当附设一个每个单链表还应当附设一个每个单链表还应当附设一个头结点头结点头结点头结点（设为（设为（设为（设为2 2个域），存个域），存个域），存个域），存v vi i信息；信息；信息；信息；adjvex nextarcinfodatafirstarc表结点表结点表结点表结点头结点头结
26、点头结点头结点邻接点域邻接点域，表表示示v vi i一个邻接一个邻接点的点的位置位置链域链域，指向指向vivi下一个边下一个边或弧的结点或弧的结点数据域数据域，与与边有关信息边有关信息（如权值）（如权值）数据域数据域，存，存储顶点储顶点vi 信信息息链域链域，指向指向单链表的第单链表的第一个结点一个结点vv 每个单链表的每个单链表的每个单链表的每个单链表的头结点另外用顺序存储头结点另外用顺序存储头结点另外用顺序存储头结点另外用顺序存储结构存储。结构存储。结构存储。结构存储。曲找揩磁冠岔芯尧励麦汤济犹去欠屁佯妆墨司令晰怨嗅啊茎挛乒收渗猫晓数据结构教学课件第7章数据结构教学课件第7章19例例例例1
27、 1：无向图的邻接表无向图的邻接表无向图的邻接表无向图的邻接表v1v2v3v5v4v4邻接表0123413341420注：注：注：注：邻接表不唯一，因各个边结点的链入顺序是任意的。邻接表不唯一，因各个边结点的链入顺序是任意的。邻接表不唯一，因各个边结点的链入顺序是任意的。邻接表不唯一，因各个边结点的链入顺序是任意的。v1v2v3v4v5231420炳助歼眉弓留屏论渗必右让哄批妈蚜遍增捡玖魔锌贬私矗辉贝囱抠素翟型数据结构教学课件第7章数据结构教学课件第7章20例例例例2 2：有向图的邻接表有向图的邻接表有向图的邻接表有向图的邻接表v1v2v3v4V4V3V2V12301邻接表邻接表(出边出边)V
28、4V3V2V13020逆邻接表逆邻接表(入边入边)吉异猎茧漆稠袒阶捕咽没豁势赔蛾跟估兵洋诱滔琢唇歇邯碰棠祝啸担佰汝数据结构教学课件第7章数据结构教学课件第7章21例例例例3 3：已知某网的邻接（出边）表，请画出该网络。已知某网的邻接（出边）表，请画出该网络。已知某网的邻接（出边）表，请画出该网络。已知某网的邻接（出边）表，请画出该网络。8064125当邻接表当邻接表的存储结的存储结构形成后，构形成后，图便唯一图便唯一确定！确定！颅颇号伟炯妄圾寺巧括菇候健店宛农哟誉腿洋矫魄伞万娟磷酚疟鱼惫狐列数据结构教学课件第7章数据结构教学课件第7章22讨论：邻接表与邻接矩阵有什么异同之处？讨论：邻接表与邻接
29、矩阵有什么异同之处？1. 1. 联系：联系：邻接表中每个链表对应于邻接矩阵中的一行，邻接表中每个链表对应于邻接矩阵中的一行，链表中结点个数等于一行中非零元素的个数。链表中结点个数等于一行中非零元素的个数。2. 2. 区别：区别： 对于任一确定的无向图，邻接矩阵是唯一的（行列对于任一确定的无向图，邻接矩阵是唯一的（行列号与顶点编号一致），但邻接表不唯一（链接次序号与顶点编号一致），但邻接表不唯一（链接次序与顶点编号无关）。与顶点编号无关）。 邻接矩阵的空间复杂度为邻接矩阵的空间复杂度为O(nO(n2 2),),而邻接表的空间复而邻接表的空间复杂度为杂度为O(n+e)O(n+e)。3. 3. 用途
30、：用途：邻接矩阵多用于稠密图的存储（邻接矩阵多用于稠密图的存储（e e接近接近n(n-n(n-1)/2)1)/2)；而邻接表多用于稀疏图的存储（；而邻接表多用于稀疏图的存储（enen2 2) )屋川扁杀窃腕宛估汗聋历永输矗孔饶榨漱愚艳倒宗羞坤骡住磐踌烷揽琴息数据结构教学课件第7章数据结构教学课件第7章23图的邻接表存储表示图的邻接表存储表示（参见教材（参见教材P163）#define MAX_VERTEX_NUM 20 /假设的最大顶点数假设的最大顶点数Typedef struct ArcNode int adjvex; /该弧所指向的顶点位置该弧所指向的顶点位置 struct ArcNode
31、 *nextarcs; /指向下一条弧的指针指向下一条弧的指针 InfoArc *info; /该弧相关信息的指针该弧相关信息的指针 ArcNode；Typedef struct VNode /顶点结构顶点结构 VertexType data; /顶点信息顶点信息 ArcNode * firstarc; /指向依附该顶点的第一条弧的指针指向依附该顶点的第一条弧的指针VNode, AdjList MAX_VERTEX_NUM ; Typedef struct /图结构图结构 AdjList vertics ; /应包含邻接表应包含邻接表 int vexnum, arcnum; /应包含顶点总数和
32、弧总数应包含顶点总数和弧总数 int kind; /还应说明图的种类（用标志）还应说明图的种类（用标志）ALGraph; /图结构图结构图的邻接表生成算法作为自测题。图的邻接表生成算法作为自测题。空间效率为空间效率为O(n+2e)O(n+2e)或或O(n+e)O(n+e)时间效率为时间效率为O(n+e*n)O(n+e*n)章这贩鳞灵携指拧花漆芹淹震宫剐秤曼趟湾逊好畦竖研骨跋勃澜奶瘟捉亏数据结构教学课件第7章数据结构教学课件第7章247.3 图的遍历图的遍历遍历定义：遍历定义：从已给的连通图中某一顶点出发，沿着一些边访遍从已给的连通图中某一顶点出发，沿着一些边访遍图中所有的顶点，且使每个顶点仅被
33、访问一次，就叫做图中所有的顶点，且使每个顶点仅被访问一次，就叫做图图图图的遍历的遍历的遍历的遍历，它是，它是，它是，它是图的图的基本运算基本运算。遍历实质：遍历实质：找每个顶点的邻接点的过程。找每个顶点的邻接点的过程。图的特点：图的特点：图中可能存在图中可能存在回路回路，且图的任一顶点都可能与其它，且图的任一顶点都可能与其它顶点相通，在访问完某个顶点之后可能会沿着某些边又回顶点相通，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点到了曾经访问过的顶点。怎样避免重复访问？怎样避免重复访问？撕塔抹褐咕炼报小版绎米媚迫院中郭宗才吼庄邓烘什核社礁猎莲辖联二擎数据结构教学课件第7章数据结构教
34、学课件第7章25一、深度优先搜索二、广度优先搜索 解决思路：解决思路：可设置一个可设置一个辅助数组辅助数组 visited n ，用来标记每个被，用来标记每个被访问过的顶点。它的初始状态为访问过的顶点。它的初始状态为0 0，在图的遍历过程中，在图的遍历过程中，一旦某一个顶点一旦某一个顶点i 被访问，就立即改被访问，就立即改 visited i为为1 1，防止，防止它被多次访问。它被多次访问。图常用的遍历：图常用的遍历：蚕蛊吧桶毋摔肩堂锻啥二檬跟屈莉碍乙拾振链氨面移悉迁锗灸屁办乏谚昔数据结构教学课件第7章数据结构教学课件第7章26一、深度优先搜索一、深度优先搜索一、深度优先搜索一、深度优先搜索(
35、 ( ( ( DFSDFSDFSDFS ) ) ) )基本思想：基本思想：仿树的先序遍历过程。仿树的先序遍历过程。Depth_First Searchv1v1v2v3v8v7v6v4v5DFS DFS 结果结果结果结果例例例例1 1 1 1：v2v4v8v5v3v6v7例例例例2 2 2 2：v2 v1 v3 v5 v2 v1 v3 v5 DFS DFS 结果结果结果结果v4 v4 v6 v6起点起点起点起点苏缝吃澜比庚溺琼吨坷岳瓮重懂誓抗蕾奔庚证瘦生蹲枪改院救致香严亢蛇数据结构教学课件第7章数据结构教学课件第7章27深度优先搜索（遍历）步骤：深度优先搜索（遍历）步骤：详细归纳：详细归纳：E在
36、访问图中某一起始顶点在访问图中某一起始顶点 v 后，由后，由 v 出发，访问出发，访问它的任一邻接它的任一邻接顶点顶点 w1；E再从再从 w1 出发，访问出发，访问与与 w1邻接邻接但还但还未被访问未被访问过的顶点过的顶点 w2；E然后再从然后再从 w2 出发，进行类似的访问，出发，进行类似的访问， E如此进行下去，直至到达所有的邻接顶点都被访问过的顶点如此进行下去，直至到达所有的邻接顶点都被访问过的顶点 u 为止。为止。E接着，退回一步，接着，退回一步，退到前一次刚访问过的顶点退到前一次刚访问过的顶点，看是否还有其，看是否还有其它没有被访问的邻接顶点。它没有被访问的邻接顶点。 如果有，如果有
37、，则访问此顶点，之后再从此顶点出发，进行与前述则访问此顶点，之后再从此顶点出发，进行与前述类似的访问；类似的访问； 如果没有，如果没有，就就再退回一步再退回一步进行搜索。重复上述过程，直到连进行搜索。重复上述过程，直到连通图中所有顶点都被访问过为止。通图中所有顶点都被访问过为止。简单归纳：简单归纳： 访问起始点访问起始点 v; 若若v的第的第1个邻接点没访问过，深度遍历此邻接点；个邻接点没访问过，深度遍历此邻接点；若当前邻接点已访问过，再找若当前邻接点已访问过，再找v的第的第2个邻接点重新遍历。个邻接点重新遍历。冰契思缺嚷嘶祟寄磅占陋印舍南邓赡包缘班器五盛歪庶客梦搅幅舱骸汐悲数据结构教学课件第
38、7章数据结构教学课件第7章28讨论讨论讨论讨论1 1：计算机如何实现计算机如何实现计算机如何实现计算机如何实现DFSDFS？1 2345610 000002 20 0000030 0000040 0000050 0000060 0000000000012345601000011 100001 11 110001 11 11 10101 11 11 111 101 11 11 11 11 11DFS DFS 结果结果结果结果邻邻接接矩矩阵阵A辅助数组辅助数组 visited n 起点起点v2v1v3v5v2v1v3v5v4v4v6v6开辅助数组开辅助数组 visited n ！例：例：1 23
39、456101 11 11 1002 21 1 00 01 1031 1 00 01 1041 1 00 001 1501 11 1 00060 001 100碳讳冤纠舰逆硫胡坝尺职鞭消端涝催绦妓历簿窗道烟貌豢赘懊酚痕怔挣针数据结构教学课件第7章数据结构教学课件第7章29讨论讨论讨论讨论2 2： DFSDFS算法如何编程？算法如何编程？算法如何编程？算法如何编程？DFS1(A, n, v) visit（v）; visitedv=1; for( j=1; j=n; j+) if ( Av, j & ! visitedj ) DFS1(A, n, j); return;可以用递归算法！可以用递归算法
40、！/Ann/Ann为邻接矩阵，为邻接矩阵，v v为起始顶点为起始顶点( (编号）编号）/访问（例如打印）顶点访问（例如打印）顶点v v / DFS1/ DFS1Av,j 1 有邻接点有邻接点visited n =0未访问过未访问过/访问后立即修改辅助数组标志访问后立即修改辅助数组标志/从从v v所在行所在行从头从头搜索邻接点搜索邻接点（教材上（教材上DFSDFS递归算法见递归算法见P169P169）玉冰祈脓秒澎便芯慢定岂世缄逢蔼康沽咙涝晌削系信恼雄鸣宛工糕申设材数据结构教学课件第7章数据结构教学课件第7章30讨论讨论讨论讨论3 3：在图的邻接表中如何进行在图的邻接表中如何进行在图的邻接表中如何
41、进行在图的邻接表中如何进行DFSDFS？v0 v1 v2 v3v0 v1 v2 v3DFS DFS 结果结果结果结果00000123辅助数组辅助数组 visited n 1000110011101111例：例：照样借用照样借用visited n ！起点起点0123注意：注意：在邻接表中，并非每个在邻接表中，并非每个链表元素（表结点）都被扫描链表元素（表结点）都被扫描到到, ,遍历速度很快。遍历速度很快。览漆厚峪距架成镊很酌墒门雌武责尧仪形蓄机驮千炮珠蜂宁相嘻冶球潮靶数据结构教学课件第7章数据结构教学课件第7章31DFS DFS 算法效率分析算法效率分析算法效率分析算法效率分析: :（设图中有设
42、图中有设图中有设图中有 n n 个顶点，个顶点，个顶点，个顶点，e e 条边条边条边条边）n如果用如果用邻接矩阵邻接矩阵来表示图，遍历图中每一个顶点来表示图，遍历图中每一个顶点都要都要从头扫描从头扫描该顶点所在行，因此遍历全部顶点该顶点所在行，因此遍历全部顶点所需的时间为所需的时间为O(n2)。n如果用如果用邻接表邻接表来表示图，虽然有来表示图，虽然有 2e 个表结点，但个表结点，但只需扫描只需扫描 e 个结点即可完成遍历，加上访问个结点即可完成遍历，加上访问 n个个头结点的时间，因此遍历图的时间复杂度为头结点的时间，因此遍历图的时间复杂度为O(n+e)。结论：结论：稠密图稠密图适于在邻接矩阵
43、上进行深度遍历；适于在邻接矩阵上进行深度遍历；稀疏图稀疏图适于在邻接表上进行深度遍历。适于在邻接表上进行深度遍历。谢梧趣呈剑狮哑严窿挪今钩署奢谷艺农汗鸦淡颧疏班此僵俩蕊耳敝瓣浪各数据结构教学课件第7章数据结构教学课件第7章32二、广度优先搜索二、广度优先搜索二、广度优先搜索二、广度优先搜索( ( ( ( BFSBFSBFSBFS ) ) ) )基本思想：基本思想：仿树的层次遍历过程。仿树的层次遍历过程。Breadth_First Searchv1v1v2v3v8v7v6v4v5BFS BFS 结果结果结果结果例例例例1 1 1 1：v2v3v4v5v6v7v8例例例例2 2 2 2：v3 v3
44、 BFS BFS 结果结果结果结果v4v4 v5 v5 起点起点起点起点v1 v2 v6 v1 v2 v6 v9 v7 v8v9 v7 v8订盆底石亚乒竿饵捅集族这越负好桶义区德肩梁沟乎沃昆捕单掌娥佯九油数据结构教学课件第7章数据结构教学课件第7章33广度优先搜索（遍历）步骤：广度优先搜索（遍历）步骤：简单归纳：简单归纳：在访问了起始点在访问了起始点v之后，依次访问之后，依次访问 v的邻接点；的邻接点；然后再依次访问这些顶点中未被访问过的邻接点；然后再依次访问这些顶点中未被访问过的邻接点；直到所有顶点都被访问过为止。直到所有顶点都被访问过为止。广度优先搜索是一种分层的搜索过程，每向前走一广度优
45、先搜索是一种分层的搜索过程，每向前走一步可能访问一批顶点，不像深度优先搜索那样有回步可能访问一批顶点，不像深度优先搜索那样有回退的情况。因此，广度优先搜索不是一个递归的过退的情况。因此，广度优先搜索不是一个递归的过程，其算法也不是递归的。程，其算法也不是递归的。似客臃衙诱啼匿立泡业夹邦喜渭奶骏块膨幕睡丰矩降邮理诲泥侗孔殊抡讶数据结构教学课件第7章数据结构教学课件第7章34BFS BFS 算法效率分析算法效率分析算法效率分析算法效率分析: :DFSDFS与与与与BFSBFS之比较：之比较：之比较：之比较：空间复杂度相同，都是空间复杂度相同，都是O(n)O(n)( (借用了堆栈或队列）；借用了堆栈
46、或队列）；时间复杂度只与存储结构时间复杂度只与存储结构（邻接矩阵或邻接表）（邻接矩阵或邻接表）有有关，而与搜索路径无关。关，而与搜索路径无关。如果使用邻接表来表示图，则如果使用邻接表来表示图，则BFS循环的总时间代价为循环的总时间代价为 d0 + d1 + + dn-1 = O(e)，其中的其中的 di 是顶点是顶点 i 的度的度。如果使用邻接矩阵，则如果使用邻接矩阵，则BFS对于每一个被访问到的顶点，对于每一个被访问到的顶点，都要循环检测矩阵中的整整一行（都要循环检测矩阵中的整整一行（ n 个元素），总的个元素），总的时间代价为时间代价为O(n2)。（设图中有设图中有设图中有设图中有 n n
47、 个顶点，个顶点，个顶点，个顶点，e e 条边条边条边条边）哆芥分墓帚败度米伎鱼掇陪陕螟三溯样肋噎吼迹戊裳柄畅慨虱寡递搭藏牲数据结构教学课件第7章数据结构教学课件第7章三、遍历应用举例三、遍历应用举例求一条从顶点求一条从顶点 i 到顶点到顶点 s 的的 简单路径简单路径澳系帮瘫菠拉渝搏接岩怯帚琐哦吧武侩虾添崭敬耻瞳汕恰靡同课扩农嘉盾数据结构教学课件第7章数据结构教学课件第7章1. 求一条从顶点求一条从顶点 i 到顶点到顶点 s 的简单路径的简单路径abchdekfg 求从顶点 b b 到顶点 k k 的一条简单路径。 从顶点 b b 出发进行深度优先搜索遍历。例如例如: : 假设找到的第一个邻
48、接点是a a，则得到的结点访问序列为: b a d h c e k f g。 假设找到的第一个邻接点是c c，则得到的结点访问序列为: b c h d a e k f g，横为贞恳琴杜吕子滑散崭赘澜臆获阵彩郡疽码赛债筑哀代胁循刷涛溯澡规数据结构教学课件第7章数据结构教学课件第7章1. 从顶点 i 到顶点 s ,若存在路径，则从顶点 i 出发进行深度优先搜索，必能搜索到顶点 s 。2. 遍历过程中搜索到的顶点不一定是路径上的顶点。结论结论:3. 由它出发进行的深度优先遍历已经完成的顶点不是路径上的顶点。驶剑柱哥蜀傈硷既混目辫摈吐俭秧羽统绵省幢艇琵湾腆饭精滚缩骨毁壤责数据结构教学课件第7章数据结构
49、教学课件第7章void DFSearch( int v, int s, char *PATH) / 从第v个顶点出发递归地深度优先遍历图G， / 求得一条从v到s的简单路径，并记录在PATH中 visitedv = TRUE; / 访问第 v 个顶点 Append(PATH, getVertex(v); / 第v个顶点加入路径 for (w=FirstAdjVex(v); w!=0&!found; w=NextAdjVex(v) ) if (w=s) found = TRUE; Append(PATH, w); else if (!visitedw) DFSearch(w, s, PATH);
50、 if (!found) Delete (PATH); / 从路径上删除顶点 v 滓公杰魏死屈恭发适素凌穷呢凉绦魄夺氨觅旁莫丽藉拾负职删赖秩如沸瞥数据结构教学课件第7章数据结构教学课件第7章397.4 7.4 图的其他运算图的其他运算1. 求图的生成树求图的生成树2. 求最小生成树求最小生成树3. 求最短路径求最短路径4.求关键路径求关键路径5. 求关节点和重连通分量（略）求关节点和重连通分量（略）6. 拓扑排序（略）拓扑排序（略）媳性并磨援沉结瞄栈彼牌务浑抚祖峻诺蛋斋创王合功一诊婿陋誓窥汉兴箔数据结构教学课件第7章数据结构教学课件第7章401.求图的生成树（或生成森林）求图的生成树（或生成森
51、林）生成树：生成树：是一个极小连通子图，它含有图中全部顶点，但只有是一个极小连通子图，它含有图中全部顶点，但只有n-1n-1条边。条边。生成森林：生成森林：由若干棵由若干棵生成树生成树组成，含全部顶点，但构成这些树组成，含全部顶点，但构成这些树的边是最少的。的边是最少的。思考1：对连通图进行遍历，得到的是什么？ 得到的将是一个极小连通子图，即图的得到的将是一个极小连通子图，即图的生成树生成树！由深度优先搜索得到的生成树，称为深度优先搜索生成树。由深度优先搜索得到的生成树，称为深度优先搜索生成树。由广度优先搜索得到的生成树，称为广度优先搜索生成树。由广度优先搜索得到的生成树，称为广度优先搜索生成
52、树。思考2：对非连通图进行遍历，得到的是什么？ 得到的将是各连通分量的生成树，即图的得到的将是各连通分量的生成树，即图的生成森林生成森林！烯协瓶秧讹剔祷啥狰弹痔攀畦吸扬兰熏汰瑰唾住蛙俊公激津荐犊泼齐乞掷数据结构教学课件第7章数据结构教学课件第7章41例例1 ：画出下图的生成树：画出下图的生成树DFS生生成成树树v0v1v2v4v4v3邻接表0123413341420v4v3v2v1v0231420v0v2v1v4v3BFS生生成成树树v0v1v3v2v4无向连通图无向连通图寥孝葡撞赣尔汪闭妮薯靡左峙囚而爆逼更返棚帛书痛沁肌击赴氧馏膊冤被数据结构教学课件第7章数据结构教学课件第7章42DEABC
53、FJLMGHIK例例2：画出下图的生成森林（或极小连通子图）：画出下图的生成森林（或极小连通子图）求解步骤：求解步骤：Step1:Step1:先求出邻接矩阵或邻接表；先求出邻接矩阵或邻接表；Step2:Step2:写出写出DFSDFS或或BFSBFS结果序列；结果序列；Step3:Step3:画出对应子图或生成森林。画出对应子图或生成森林。下面选用下面选用邻接表邻接表方式来求方式来求深度深度优先搜索生成森林优先搜索生成森林注：亦可由邻接矩阵或邻接表直接画出生成森林注：亦可由邻接矩阵或邻接表直接画出生成森林膜湛帅窘搭卫掖锋霄飘诗则啪啪睹喳磁恒缓追牲信姥倍丝俊孽膳郸厦魔垫数据结构教学课件第7章数据
54、结构教学课件第7章43115 5M12L11K10J9I8H7G6F5E4D3C2B1A01201200437810661011126709121911112294710811DEGHIK子图子图1：再写出再写出DFS结果（结果（3次）次）ABMJLCFDEGHKIABCFJLM先写出邻接表（或邻接矩阵）：先写出邻接表（或邻接矩阵）：子图子图2：子图子图3：最小连通！最小连通！躁雇瘴乱湛泥灰陇豢蕊昨恋误嵌泌讨穴密徽坏荫渤窥迟擎炒辆锡舰抬佣本数据结构教学课件第7章数据结构教学课件第7章44DEGHIK子图子图(或连通分量或连通分量)ABCFJLMABCFJLMDEGHIK生生成成森森林林蛆训憋武
55、逼脂迅秧宵涉难囱枷缓训驾戌仁打畦琢顶捷旦孵击墙熄锌杂磐宇数据结构教学课件第7章数据结构教学课件第7章452. 2. 求最小生成树求最小生成树首先明确：首先明确：使用不同的遍历图的方法，可以得到不同的生成树；从使用不同的遍历图的方法，可以得到不同的生成树；从不同的顶点出发，也可能得到不同的生成树。不同的顶点出发，也可能得到不同的生成树。按照生成树的定义，按照生成树的定义，n n 个顶点的个顶点的连通网络连通网络的生成树有的生成树有 n n 个顶点、个顶点、n-n-1 1 条边。条边。即有权图即有权图目标：目标：在网络的多个生成树中，寻找一个在网络的多个生成树中，寻找一个各边权值之和最小各边权值之
56、和最小的的生成树。生成树。构造最小生成树的准则构造最小生成树的准则v必须只使用该网络中的必须只使用该网络中的边边来构造最小生成树；来构造最小生成树；v必须使用且仅使用必须使用且仅使用n n-1-1条边条边来联结网络中的来联结网络中的n n个顶点；个顶点；v不能使用产生回路的边。不能使用产生回路的边。晨哗膳眺莉童鲸粪敬躇掌惭忠呻郑寡昧症渐岭嘎匿呸替捣防岿俞宏惮析帜数据结构教学课件第7章数据结构教学课件第7章46欲在欲在n n个城市间建立通信网，则个城市间建立通信网，则n n个城市应铺个城市应铺n-1n-1条线路；但条线路；但因为每条线路都会有对应的经济成本，而因为每条线路都会有对应的经济成本，而
57、n n个城市可能有个城市可能有n(n-n(n-1)/2 1)/2 条线路，那么，条线路，那么，如何选择如何选择n n1 1条线路，使总费用最少？条线路，使总费用最少？典型用途：典型用途：数学模型：数学模型：顶点顶点表示城市，有表示城市，有n n个；个；边边表示线路，有表示线路，有n n1 1条；条；边的权值边的权值表示线路的经济代价；表示线路的经济代价；连通网连通网表示表示n n个城市间通信网。个城市间通信网。显然此连通网是显然此连通网是一个一个生成树！生成树！问题抽象：问题抽象： n个顶点的生成树很多，需要从中选一棵个顶点的生成树很多，需要从中选一棵代价最小代价最小的生成树，即该树的生成树，
58、即该树各边的代价之和各边的代价之和最小。此树便称为最小生最小。此树便称为最小生成树成树MST(Minimum cost Spanning Tree)啥省疮骄谓拓永纸絮慑音翟禄沃钥奔拉簿奏升择迁讣哮酗捡憾盆超棚黎郎数据结构教学课件第7章数据结构教学课件第7章47讨论：如何求得最小生成树？讨论：如何求得最小生成树？有多种算法，但最常用的是以下两种：有多种算法，但最常用的是以下两种：最小生成树的最小生成树的最小生成树的最小生成树的 MST MST 性质如下：性质如下：性质如下：性质如下：vKruskal（克鲁斯卡尔克鲁斯卡尔）算法）算法vPrim（普里姆普里姆）算法）算法 KruskalKruska
59、l算法特点：算法特点：将边归并将边归并，适于求，适于求稀疏网稀疏网的最小生成树。的最小生成树。PrimePrime算法特点算法特点: : 将顶点归并将顶点归并，与边数无关，适于，与边数无关，适于稠密网稠密网。这两个算法，都是利用这两个算法，都是利用MST 性质来构造最小生成树的。性质来构造最小生成树的。若若U集是集是V的一个非空子集，若的一个非空子集，若(u0, v0)是一条是一条最小权值的边最小权值的边，其中其中u0 U，v0 V-U；则：；则：(u0, v0)必在最小生成树上必在最小生成树上。 菏疯恨缉恨玄鸡奖妙唯安氨蔷蛤冯钳廉需搐石亩勤烙沥下咀袄哩痢耳了晕数据结构教学课件第7章数据结构教
60、学课件第7章48步骤步骤步骤步骤：(1) (1) 首首先构造一个只有先构造一个只有 n n 个顶点但没有边的非连通图个顶点但没有边的非连通图 T T = = V V, , , , 图中每个顶点自成一个连通分量。图中每个顶点自成一个连通分量。(2) (2) 当在边集当在边集 E E 中选到一条具有最小权值的边时中选到一条具有最小权值的边时, ,若该若该边的两个顶点落在边的两个顶点落在T T中不同的连通分量上，则将此中不同的连通分量上，则将此边加入到生成树的边加入到生成树的边集合边集合T T 中；否则将此边舍去，中；否则将此边舍去，重新选择一条权值最小的边。重新选择一条权值最小的边。(3) (3)
61、 如此重复下去，直到所有顶点在同一个连通分量上如此重复下去，直到所有顶点在同一个连通分量上为止。此时的为止。此时的T T即为所求（即为所求（最小生成树最小生成树）。）。克鲁斯卡尔（克鲁斯卡尔（Kruskal）算法）算法:设设N N = = V V, , E E 是有是有 n n 个顶点的连通网，个顶点的连通网，Kruskal算法采用算法采用邻接表邻接表作为图的存储表示作为图的存储表示尺虐怪彩顿崎乔桅冶稠窿但体姜鱼苔极沛坠械击榔无茫躬彻京报纳滦裹扑数据结构教学课件第7章数据结构教学课件第7章49例：应用克鲁斯卡尔算法构造最小生成树的过程例：应用克鲁斯卡尔算法构造最小生成树的过程酉挛窑操框囊歧溅咕
62、谊商硕蔡钢屑捉军暮贰洞蔽有蒲拈称忽撮腥卸狼行烯数据结构教学课件第7章数据结构教学课件第7章507.4 7.4 图的其他运算图的其他运算1. 求图的生成树求图的生成树2. 求最小生成树求最小生成树3. 求最短路径求最短路径4.求关节点和重连通分量（略）求关节点和重连通分量（略）5.拓扑排序（略）拓扑排序（略）6.求关键路径（略）求关键路径（略）映顿恭曳掇萎浅试质萌抱缸氮曼擎恳屉饶觉泞牛嗡班奄求履懊察渍卢囚嗜数据结构教学课件第7章数据结构教学课件第7章511. 求图的生成树求图的生成树生成树的特征生成树的特征n n 个顶点的个顶点的连通网络连通网络的的生成树有生成树有 n n 个顶点、个顶点、n-
63、n-1 1 条边。条边。求生成树的方法求生成树的方法DFSDFS（深度优先搜索）（深度优先搜索）和和BFSBFS（广度优先搜索）（广度优先搜索）附：附：求最大连通分量的方法求最大连通分量的方法 只能用只能用DFSDFS（深度优先搜索）（深度优先搜索）憾岭苹乏蕴隐艰仆候裤虎睦皖块燎擂究冯工苯似抡忙枚褒义名蹈酮茬尤认数据结构教学课件第7章数据结构教学课件第7章522. 2. 求最小生成树求最小生成树目标：目标：在网的多个生成树中，寻找一个在网的多个生成树中，寻找一个各边权值之和最各边权值之和最小小的生成树。的生成树。应用：应用： n n个城市建网，如何选择个城市建网，如何选择n n1 1条线路，使
64、总费用最少？条线路，使总费用最少？vKruskal（克鲁斯卡尔克鲁斯卡尔）算法）算法vPrim（普里姆普里姆）算法）算法 算法：算法：任何一个无向连通图的最小生成树只有一种任何一个无向连通图的最小生成树只有一种归并边归并边归并顶点归并顶点驳绳崎苟雪棒批亦桨吞漆肚幅箔缀篮宵暮廖矢污忧崭岁鼓厘石彰捕羡泰乖数据结构教学课件第7章数据结构教学课件第7章53KruskalKruskal（克鲁斯卡尔）算法（克鲁斯卡尔）算法例例 ：1 14 46 65 52 23 31 15 56 65 55 54 46 63 36 62 21 15 54 43 32 21 13 35 52 24 46 6随匙磷柜南跳乡满
65、够淤余溶杯赋摔呸苛檀惮竭翟贡痢瓶勿可篙省堤沤骏短数据结构教学课件第7章数据结构教学课件第7章54计算机内怎样实现计算机内怎样实现KruskalKruskal算法？算法？设计思路：设计思路：设计思路：设计思路： 设每条边对应的结构类型为：设每条边对应的结构类型为：特点：特点：将将边边归并归并适于求适于求稀疏网稀疏网的最小生成树。的最小生成树。 故采用故采用邻接表邻接表作为图的存储表示。作为图的存储表示。LchildLchildv vi iv vj jweightweightRchildRchild 取堆顶元素，加入到对应最小生成树的新邻接表中（初始取堆顶元素，加入到对应最小生成树的新邻接表中（初
66、始为空），从堆中删除它并重新排序堆，每次耗时为空），从堆中删除它并重新排序堆，每次耗时loglog2 2(e)(e)； 重复上一步，注意每次加入时要判断是否重复上一步，注意每次加入时要判断是否“多余多余”（即是（即是否已被新表中的连通分量包含）；否已被新表中的连通分量包含）； 直到堆空。直到堆空。显然，显然， Kruskal Kruskal算法的时间效率算法的时间效率O O（elogelog2 2e e）初态：初态：按权值排序按权值排序( (以以堆排序堆排序为佳，堆顶即为权值最小的边）为佳，堆顶即为权值最小的边）芝剖肮犀盏吕律筏企溜诗骆输册牵花鹃钙镰恍哺谬独沏盒托壤巷琼谓帆坯数据结构教学课件第
67、7章数据结构教学课件第7章55（1 1）初始状态：）初始状态： U =u0 ,（ u0 V ），）， TE= ,（2 2）从）从E中选择顶点分别属于中选择顶点分别属于U、V-U两个集合、且权值两个集合、且权值最小的边最小的边（ u0, v0)，将顶点将顶点v0归并到集合归并到集合U中中，边边（u0, v0)归并到归并到TE中中；（3 3）直到）直到U=V为止。此时为止。此时TETE中必有中必有n-1n-1条边，条边， T（V，TE）就是最小生成树。就是最小生成树。设：设：N =N =（V , EV , E）是个连通网，）是个连通网，另设另设U U为最小生成树的顶点集，为最小生成树的顶点集，TE
68、TE为最小生成树的边集。为最小生成树的边集。构造步骤构造步骤: :普利姆（普利姆（PrimPrim）算法）算法张轴戈巧趋锨商评睹扩魂拢帜熊峻践陶遍倔梦跃遭婆腑故殿怂莎争填做池数据结构教学课件第7章数据结构教学课件第7章56例：例：1 14 46 65 52 23 31 15 56 65 55 54 46 63 36 62 23 36 64 42 25 51 1 注注 ：在最小生成树的生成过程中，所选的边都是：在最小生成树的生成过程中，所选的边都是 一端在一端在V-U中，另一端在中，另一端在U中。中。瑞帅离旨银伏诣仑多亏严汉蒸焉哆您箍炽水趟埋骤哼槐卢式前酮侨狄钟荡数据结构教学课件第7章数据结构教
69、学课件第7章57设计思路：设计思路：设计思路：设计思路： 增设一辅助数组增设一辅助数组Closedge n ， 每个每个数组分量都数组分量都有两个域：有两个域：要求：要求：使使Colsedge i.lowcost = min( ( u ,vi ) ) u U 计算机内怎样实现计算机内怎样实现PrimPrim（普里姆）算法？（普里姆）算法？ PrimePrime算法算法特点特点: : 将顶点归并将顶点归并，与边数无关，适于稠密网。，与边数无关，适于稠密网。 故采用故采用邻接矩阵邻接矩阵作为图的存储表示。作为图的存储表示。adjvexadjvexlowcostlowcostv vi i 在在U中的
70、邻点中的邻点u uColsedge iV-U中顶点中顶点v vi iu与与vi之间对应的边权之间对应的边权从从u1un中挑中挑赖陀疏婴著窿畔肮沁芝按喀掐春妆螟顽渐澡你观捷惕篇荔栈屁返厌粥邵标数据结构教学课件第7章数据结构教学课件第7章58vexlowcostvexlowcostvexlowcostvexlowcostvexlowcostvexlowcostV-UU65432vclosedge1423561655536426具体示例：具体示例：具体示例：具体示例：12,3,4,5,6161115111, 32, 4, 5, 60351536341,3,62, 4,5350623601,3,6,4
71、2, 535036001,3,6,4,25000023000001,3,6,4,2,513起点起点46245235123456显然，显然， Prim Prim算法的时间效率算法的时间效率O O（n n2 2）裂红耳斤豆心义巾立耀捍据努阜巷糙钦复苗仗弄淳喉将疆观西哦囤海瞳笨数据结构教学课件第7章数据结构教学课件第7章59一顶点到其一顶点到其余各顶点余各顶点3. 3. 求最短路径求最短路径两种常见的最短路径问题：两种常见的最短路径问题：一、一、 单源最短路径单源最短路径用用Dijkstra（迪杰斯特拉）（迪杰斯特拉）算法算法二、所有顶点间的最短路径二、所有顶点间的最短路径用用Floyd（弗洛伊德）
72、（弗洛伊德）算法算法典型用途：典型用途：交通问题。如：城市交通问题。如：城市A A到城市到城市B B有多条线路，但每条有多条线路，但每条线路的交通费（或所需时间）不同，那么，线路的交通费（或所需时间）不同，那么，如何选择一条线路，如何选择一条线路，使总费用（或总时间）最少？使总费用（或总时间）最少？问题抽象：问题抽象：在带权有向图中在带权有向图中A A点（源点）到达点（源点）到达B B点（终点）的多点（终点）的多条路径中，寻找一条条路径中，寻找一条各边权值之和最小各边权值之和最小的路径，即最短路径。的路径，即最短路径。（注：最短路径与最小生成树不同，路径上不一定包含（注：最短路径与最小生成树不
73、同，路径上不一定包含n n个顶点）个顶点）任意两顶任意两顶点之间点之间复暇怒坚财钳偿垮烯虞仁疫秉搀明倘搽处埃浅延琶侥氮挂罐钙惕经徽呈矾数据结构教学课件第7章数据结构教学课件第7章60一、单源最短路径一、单源最短路径 ( (Dijkstra算法算法) )目的：目的： 设一设一有向图有向图G=G=（V, EV, E），已知各边的权值，以某指），已知各边的权值，以某指定点定点v v0 0为源点，求从为源点，求从v v0 0到图的其余各点的最短路径。到图的其余各点的最短路径。限定限定各各边上的权值大于或等于边上的权值大于或等于0 0。例例1 1：源点源点从从FAFA的路径有的路径有4 4条：条： FA
74、 FA： 24 24 FBA FBA： 5 518=2318=23 FBCA FBCA：5+7+9=215+7+9=21 FDCAFDCA：25+12+9=3625+12+9=36又：又：从从FBFB的最短路径是哪条？的最短路径是哪条？从从FCFC的最短路径是哪条？的最短路径是哪条？睡醇站惕拟笑游嫁漾甥师皋擦挑停磁脚瞬厚恩形堆沁因休汰隙蜜账肛阮蓖数据结构教学课件第7章数据结构教学课件第7章61v0(v0, v1)10源点源点终点终点 最最 短短路路 径径路径长度路径长度(v0, v1, v2) (v0, v3, v2)(v0, v3)30 v1 v2 v3 v4100(v0, v4)(v0,
75、v3, v4)(v0, v3, v2, v4)例例2： 6001234 5090 70讨论：计算机如何自动求出这些最短路径？讨论：计算机如何自动求出这些最短路径？(v0, v1, v2, v4)60侨绦协奎襄挡葬睬灭博箭谦鸳诡芍件锣瞻彰侧虹溅辰坦快磋往敦奄孺釉酱数据结构教学课件第7章数据结构教学课件第7章62Dijkstra（迪杰斯特拉）算法（迪杰斯特拉）算法算法思想：算法思想：先找出从源点先找出从源点v v0 0到各终点到各终点v vk k的直达路径（的直达路径（v v0 0,v,vk k），即），即通过一条弧到达的路径。通过一条弧到达的路径。从这些路径中找出一条长度最短的路径（从这些路径中
76、找出一条长度最短的路径（v v0 0,u,u）, ,然后然后对其余各条路径进行适当调整：对其余各条路径进行适当调整：若在图中存在弧（若在图中存在弧（u,vu,vk k），且（），且（v v0 0,u,u）+ +（u,vu,vk k） （v v0 0,v,vk k）, ,则以路径（则以路径（v v0 0,u,v,u,vk k）代替（）代替（v v0 0,v,vk k）。）。在调整后的各条路径中，再找长度最短的路径，依此在调整后的各条路径中，再找长度最短的路径，依此类推。类推。总之，按路径总之，按路径“长度长度” 递增的次序来逐步产生最短路径递增的次序来逐步产生最短路径喇偷王卢吓颜捎必近溜略貉穆搅
77、慰香拉声窍奈烬桌促旨啤亏葱腕哟唐片咎数据结构教学课件第7章数据结构教学课件第7章63算法描述：算法描述：（1 1）设设AnnAnn为有向网的带权为有向网的带权邻接矩阵邻接矩阵，AijAij表示弧表示弧（vi，vj ) )的权值，的权值，S S为已找到从源点为已找到从源点v v0 0出发的最短路径的终点集合，它的初出发的最短路径的终点集合，它的初始状态为始状态为 v v0 0 .辅助数组辅助数组distn为各终点当前找到的最短路径的长为各终点当前找到的最短路径的长度，它的初始值为度，它的初始值为： distiAAv v0 0,i ,i /即邻接矩阵中第即邻接矩阵中第v v0 0行的权值行的权值（
78、2 2）选择选择u u，使得，使得 distumindistw | mindistw | wV-SwV-S / w/ w是是S S集之外的顶点集之外的顶点 / distu / distu是从源点是从源点v v0 0到到S S集外所有顶点的弧中最短的一条集外所有顶点的弧中最短的一条 S= S u S= S u /将将u u加入加入S S集集（3 3）对于所有不在对于所有不在S S中的终点中的终点w w，若，若 distu+ AAu,wu,w distw distw / / 即即(v v0 0,u),u)(u,w)(v(u,w)(v0 0,w),w)则修改则修改distwdistw为：为： dis
79、tw distw distu+ AAu,wu,w （4 4）重复操作（重复操作（2 2）、（）、（3 3）共）共n-1n-1次，由此求得从次，由此求得从v v0 0到各终点到各终点的最短路径。的最短路径。全敌萤榜满梦契丽昆乡振泅胯泵犀盏妊威滤课籽掳肮肌徐孜节喷姆喘陛擦数据结构教学课件第7章数据结构教学课件第7章64算法的算法的C语言程序见教材语言程序见教材P189；Void ShortPath_DIJ(Mgraph G, int v0, PathMatrix &P, ShortPathTable &D)for(v=0; vG.vexnum; +v) Finalv=false;Dv= G.arc
80、sv0v; for(w=0;w G.vexnum;+w) Pvw= false; /设空路径设空路径 if(DvINFINITY)Pvv0=true; Pvv= true; /forDv0=0; finalv0=true;For(i=1;iG.vexnum;+i)盎谣镀满式闻渴原隶讫辞英座玫胶谅矛靛亢亚渐窑旬鲸近塔敞岗狂舶苑扰数据结构教学课件第7章数据结构教学课件第7章655540312100603010102050例例3：0123450 1 2 3 4 5与最小生成树的不同点：路径可能是累加的！与最小生成树的不同点：路径可能是累加的！仪曰徊捅矾扫骑讹汕用鞘浩右加羔锚廖飞龚袭寡削镰舱硕叛礁星笛
81、块掖中数据结构教学课件第7章数据结构教学课件第7章66(v0,v2)+ (v2,v3)(v0,v3)终终点点 从从v0到各终点的到各终点的dist值和最短路径值和最短路径v1v2v3v4v5vjS S之外的当前最之外的当前最短路径之顶点短路径之顶点60v0,v2,v350v0,v4,v330v0,v490v0,v4, v560v0,v4,v3,v5sv0,v2v0 ,v2 ,v4v0 ,v2 ,v4 ,v3 v0 ,v2 ,v4 ,v3 ,v510v0,v2 30v0,v4100v0, v5v2v4v3v5100v0, v5distwdistw 10v0,v250v0,v4,v330v0,v4
82、视失叔钦社掸陕骤妈尹饵伪碎讳恕虎偶刽谬扎甥淤村侮袍华峻解贤眶馏亿数据结构教学课件第7章数据结构教学课件第7章67二、二、所有顶点之间的所有顶点之间的最短路径最短路径问题的提出：问题的提出：已知一个各边权值均大于已知一个各边权值均大于0 0的带权有的带权有向图，对每一对顶点向图，对每一对顶点 vi vj，希望求出希望求出vi 与与vj之间之间的最短路径和最短路径长度。的最短路径和最短路径长度。解决思路：解决思路：可以通过可以通过调用调用n n次次Dijkstra算法算法来完成，但时间复杂来完成，但时间复杂度为度为O(n3)。改进：改进：Floyd算法（略）算法（略） 芦怕川何阴匠朝铲把锭滩试赵储
83、洽蔫春叠盖送巾顾石溶浪喻屉曰咙勒止羽数据结构教学课件第7章数据结构教学课件第7章68图图存储结构存储结构遍遍 历历邻接矩阵邻接矩阵邻邻 接接 表表十字链表十字链表邻接多重表邻接多重表深度优先搜索深度优先搜索DFSDFS广度优先搜索广度优先搜索DFSDFS无向图的应用无向图的应用应用应用图的连通分量图的连通分量图的生成树图的生成树图的生成树图的生成树最小生成树最小生成树Prim算法算法Kruskal算法算法有向有向(无环无环)图的应用图的应用最短路径最短路径Dijkstra算法算法Floyd算法算法（利用（利用DFSDFS）本章小结本章小结( (利用利用DFSDFS和和BFS)BFS)孔踌哀唾砚条值噪仗犬促步抉哦撰茅阅钵岔衫碳场病椒驰尚设完烹廉判蠕数据结构教学课件第7章数据结构教学课件第7章
