数据结构(c语言版)_严蔚敏版_第7章_图2_信大(第11讲)

1、数据的逻辑结构数据的逻辑结构 线性结构线性结构 非线性结构非线性结构线性表线性表栈栈队队树形结构树形结构图形结构图形结构串串多对多多对多（m:n)从图的任一顶点出发访问图中的各个顶点，从图的任一顶点出发访问图中的各个顶点，并且使并且使每个顶点仅被访问一次每个顶点仅被访问一次。这一过程叫做。这一过程叫做图图的遍历的遍历。对图的遍历通常采用两种遍历次序，即对图的遍历通常采用两种遍历次序，即深度深度优先搜索优先搜索（DFS）和）和广度优先搜索广度优先搜索（BFS）。）。7.3.1 深度优先搜索（深度优先搜索（DFS）基本思想是基本思想是:从图从图G的某个的某个顶点顶点V0出发出发，访问，访问V0，然

2、后，然后选择一个选择一个与与V0相邻且未被访问的顶点相邻且未被访问的顶点Vi访问，再从访问，再从Vi出发选出发选择一个与择一个与Vi相邻且未被访问的顶点相邻且未被访问的顶点Vj进行访问，依此继续。进行访问，依此继续。如果当前被访问的顶点的所有相邻顶点都已被访问，则如果当前被访问的顶点的所有相邻顶点都已被访问，则退退回到已被访问顶点序列中最后一个拥有未被访问的相邻顶回到已被访问顶点序列中最后一个拥有未被访问的相邻顶点点W，从，从W出发按同样方法向前遍历，直到图中所有顶点出发按同样方法向前遍历，直到图中所有顶点都被访问到为止。都被访问到为止。特点是尽可能向特点是尽可能向纵深方向纵深方向进行搜索。进

3、行搜索。一 深度优先遍历(深度优先搜索)1）从中某顶点）从中某顶点v（起始点）出发，访问该顶点；（起始点）出发，访问该顶点；2）依次从）依次从v的未被访问的邻接点出发，继续对图的未被访问的邻接点出发，继续对图 进行深度优先遍历。进行深度优先遍历。直至图中所有和直至图中所有和v有路径有路径 相通的顶点都被访问到相通的顶点都被访问到； 3）若图中尚有顶点未被访问，则另选一个未被访）若图中尚有顶点未被访问，则另选一个未被访 问顶点作起始点，重复问顶点作起始点，重复1）、）、 2），），直至图中直至图中 所有顶点都被访问到为止所有顶点都被访问到为止。 V0 V7 V6 V5 V4 V3 V2 V1图图

4、G步骤：步骤：说明：说明：(强强)连通图连通图的遍历只须执行的遍历只须执行1）和）和 2）两步。）两步。 V0 V7 V6 V5 V4 V3 V2 V1,V6例求图求图G以以V0起始点的的深度优先序列起始点的的深度优先序列V0V1V3V2V7V5 V4V0 ,V1 ,V4 ,V7 ,V3 ,V2 ,V5 ,V6 V0 ,V1,V3,V7,V4,V2,V5图图GV6由于没有规定访问邻接点的由于没有规定访问邻接点的顺序，深度优先序列不唯一顺序，深度优先序列不唯一12345678例求求下下图以图以1起始点的的深度优先序列起始点的的深度优先序列 1,2,4,8,5,6,3,7DFS搜索顺序 V1V2V

5、4V5V3V7V6V8深度遍历： V1 V2 V4 V8 V5 V6 V3 V7例求求下下图以图以V1起始点的的深度优先序列起始点的的深度优先序列7.3.2 广度优先搜索（广度优先搜索（BFS）基本思想是基本思想是:首先访问首先访问初始点初始点Vi，并将其，并将其标记标记为已访问为已访问过，接着访问过，接着访问Vi的所有未被访问过的邻接点的所有未被访问过的邻接点Vi1，Vi2，Vit ，并均标记为已访问过，然后再按照，并均标记为已访问过，然后再按照Vi1，Vi2，Vit的次序，访问每一个顶点的所有未被访问过的邻接点，并的次序，访问每一个顶点的所有未被访问过的邻接点，并均标记为已访问过，依此类推

6、，直到图中所有和初始点均标记为已访问过，依此类推，直到图中所有和初始点Vi有路径相通的顶点都被访问过为止。有路径相通的顶点都被访问过为止。这种搜索方式类似于树的按这种搜索方式类似于树的按层次遍历层次遍历的过程。的过程。用先进先出的用先进先出的队列队列来记录这些顶点。来记录这些顶点。 V0 V7 V6 V5 V4 V3 V2 V1从图中从图中某未访问过的顶点某未访问过的顶点vi出发：出发：1）访问顶点）访问顶点vi ；2）依次访）依次访问问 vi 的所有未被访问的邻接点；的所有未被访问的邻接点；3）从这些邻接点出发，访问它们的所有未被访问的）从这些邻接点出发，访问它们的所有未被访问的邻接点邻接点

7、; 依此类推，直到图中所有的顶点的邻接依此类推，直到图中所有的顶点的邻接点都被访问。点都被访问。V0V1V3V2V7V6V5V4由于没有规定由于没有规定访问邻接点的顺序，访问邻接点的顺序，广度优先序列不唯一。广度优先序列不唯一。例例求图求图G 的以的以V0起点的的广度优先序列起点的的广度优先序列 V0,V1,V2,V3,V4,V5,V6,V7Vw1w8w3w7w6w2w5w4对连通图，从起始点对连通图，从起始点V到其余各顶点必存在路径。到其余各顶点必存在路径。 其中其中，V-w1, V-w2, V-w8 的路径长度为的路径长度为1;V-w7, V-w3, V-w5的的路径长度为路径长度为2 ;

8、 ;V-w6, V-w4 的路径长度为的路径长度为3。w1Vw2w7w6w3w8w5w4说明：说明：在广度优先遍历图时，在广度优先遍历图时， “先被访问的顶点的邻接点先被访问的顶点的邻接点” 先于先于“后被访问的顶点的邻后被访问的顶点的邻 接点接点”被访问。被访问。即以即以V为为 起始点，起始点，由近至远由近至远，依次依次访访 问和问和V有路径相通且有路径相通且路径长度路径长度 为为1，2，的顶点。的顶点。 广度优先搜索广度优先搜索(Breadth First Search)遍历类似遍历类似于树的按层次遍历。于树的按层次遍历。 (1)首先访问图中某一个指定的出发点首先访问图中某一个指定的出发点

9、vi； (2)然后然后依次访问依次访问vi的所有邻接点的所有邻接点vi1,vi2vit； (3)再依次以再依次以vi1,vi2vit为顶点，访问各顶点未为顶点，访问各顶点未被访问的邻接点，依此类推，直到图中所有顶点均被访问的邻接点，依此类推，直到图中所有顶点均被访问为止。被访问为止。 p 广度优先搜索的思想广度优先搜索的思想12345678例求求下下图以图以1起始点的的起始点的的广广度优先序列度优先序列 4,2,8,1,5,6,7,3BFS搜索顺序V1V2V4V5V3V7V6V8广度遍历：广度遍历： V1 V2 V3 V4 V5 V6 V7 V8例求求下下图以图以V1起始点的的起始点的的广广度

10、优先序列度优先序列练习1、从顶点、从顶点V0出发，分别采用深度优先搜索出发，分别采用深度优先搜索算法和广度优先搜索算法对右图进行遍历算法和广度优先搜索算法对右图进行遍历所得到的搜索序列及其生成树。所得到的搜索序列及其生成树。【答案】【答案】深度优先搜索：深度优先搜索：序列：序列：V0V1V3V2V4广度优先搜索：广度优先搜索：序列：序列：V0V1V2V4V3练习2、从顶点、从顶点V0出发，分别采用深度优先出发，分别采用深度优先搜索算法和广度优先搜索算法对右图进搜索算法和广度优先搜索算法对右图进行遍历所得到的搜索序列及其生成树。行遍历所得到的搜索序列及其生成树。【答案】【答案】深度优先搜索：深度

11、优先搜索：序列：序列：V0V5V1V2V3V4广度优先搜索：广度优先搜索：序列：序列：V0V5V1V4V2V3最小生成树问题，即在连通网中，构造边上的代价最小生成树问题，即在连通网中，构造边上的代价总和最小（即权值之和为最小的）。总和最小（即权值之和为最小的）。求解最小生成树问题的算法有两个求解最小生成树问题的算法有两个:即即普里姆算法普里姆算法（Prim）和）和克鲁斯卡尔算法克鲁斯卡尔算法（Kruskal）。）。 生成树定义生成树定义l图的遍历过程中经过的图的遍历过程中经过的n个顶点个顶点n-1条边条边即为一即为一棵生成树。棵生成树。在无向连通图在无向连通图G G中，其一个极小连通子图中，其

12、一个极小连通子图( (无回无回路路) )是是G G的生成树，它含有图中全部的生成树，它含有图中全部n n个顶点个顶点，但，但只有只有n-1n-1条边条边，且不唯一。，且不唯一。深度优先生成树：按深度优先遍历生成的深度优先生成树：按深度优先遍历生成的生成树生成树c0c1c3c2c4c5例例c0c1c3c2c4c5c0c1c3c2c4c5c0c1c3c2c4c5广度优先生成树：按广度优先遍历生成的广度优先生成树：按广度优先遍历生成的生成树生成树非连通图的生成森林非连通图的生成森林V0V1V3V4V2V6V8V7V5V9（a）不连通的无向图）不连通的无向图G12V0V1V3V4V2V8V7V9V6V

13、5（c）图）图G12的一个的一个BFS生成森林生成森林V0V1V3V4V2V6V8V7V5V9（b）图）图G12的一个的一个DFS生成森林生成森林 要在要在 n 个城市间建立个城市间建立通讯网，如何在保证通讯网，如何在保证 n 个城市连通的前题下最节个城市连通的前题下最节省经费省经费? ABCDEF101015121287665无向网无向网G1ABCDEF10101276花费：花费：45ABCDEF1512865花费：花费：465ABCDEF107610花费：花费：38 要在要在 n 个城市间建立个城市间建立通讯网，如何在保证通讯网，如何在保证 n 个城市连通的前题下最节个城市连通的前题下最节

14、省经费省经费? ABCDEF101015121287665这个问题实际上是连通图的最小生成树问这个问题实际上是连通图的最小生成树问题。题。ABCDEF1010151212876655ABCDEF107610最小生成树的定义最小生成树的定义若图若图G G是带权的无向连通图（连通网），生成树上各是带权的无向连通图（连通网），生成树上各边权值之和称为生成树的代价，边权值之和称为生成树的代价，代价最小的生成树代价最小的生成树称为最小生成树；称为最小生成树；ln n个顶点、个顶点、n-1n-1条边、权值之和最小。条边、权值之和最小。1654327131791812752410连通网：连通网：165432

15、1397510生成树生成树1：1654327139724生成树生成树2：代价：代价：44代价：代价：60最小生成树最小生成树如何快速有效地构造如何快速有效地构造最小生成树最小生成树 构造最小生成树的准则：构造最小生成树的准则：l必须只使用该网络中的边来构造最小生成树；必须只使用该网络中的边来构造最小生成树；l必须使用且仅使用必须使用且仅使用n-1条边来联接网络中的条边来联接网络中的n个顶点个顶点7.4.1 普里姆算法（普里姆算法（Prim）算法思想算法思想: 按照将顶点逐个连通的步骤，把已连通的顶按照将顶点逐个连通的步骤，把已连通的顶点加入到集合点加入到集合U中，这个集合中，这个集合U开始时为

16、空集。开始时为空集。首先任选一首先任选一个顶点加入个顶点加入U，然后从依附于该顶点的边中，然后从依附于该顶点的边中选取权值最小的选取权值最小的边边作为生成树的一条边，并作为生成树的一条边，并将依附于该边且在集合将依附于该边且在集合U外的另外的另一顶点加入到一顶点加入到U，表示这两个顶点已通过权值最小的边连通，表示这两个顶点已通过权值最小的边连通了。以此类推，直到全部顶点加入到了。以此类推，直到全部顶点加入到U。Prim(普里姆普里姆)算法思想算法思想 设原连通网设原连通网G=(V, E)G=(V, E)，生成的最小生成树，生成的最小生成树T=(U, T=(U, TE)TE)，则算法步骤如下：，

17、则算法步骤如下：(1)(1)任选一个顶点任选一个顶点u u0 0放入放入U U中，即初始中，即初始U=uU=u0 0 ，TE= TE= (2)(2)找连接找连接U U与与V-UV-U集合的一条权值最小的边集合的一条权值最小的边即找即找顶点顶点uU,uU,顶点顶点vV-UvV-U的权值最小的一条边的权值最小的一条边(u,v)E(u,v)E；并把顶点并把顶点v v加入到加入到U U中，边中，边(u,v) (u,v) 加入到加入到TETE中，中，即修改即修改U=U+v,TE=TE+(u,v)U=U+v,TE=TE+(u,v)(3)(3)转到（转到（2 2）重复执行，直到）重复执行，直到U=VU=V结

18、束结束ABCDEF101015121287665（a）无向网）无向网G1算法演示算法演示:Prim算法求解最小生成树算法求解最小生成树BCE101512（b）求解过程）求解过程67ABCDEF1010151212865（a）无向网）无向网G1算法演示算法演示:Prim算法求解最小生成树算法求解最小生成树CDEF101512765（b）求解过程）求解过程ABCDEF101015121287665 （a）无向网）无向网G1算法演示算法演示:Prim算法求解最小生成树算法求解最小生成树CDEF1015765（b）求解过程）求解过程6ABCDEF10101512128765 （a）无向网）无向网G1算

19、法演示算法演示:Prim算法求解最小生成树算法求解最小生成树CEF1015765（b）求解过程）求解过程6ABCDEF10101512128765 （a）无向网）无向网G1算法演示算法演示:Prim算法求解最小生成树算法求解最小生成树CEF10157665（b）求解过程）求解过程ABCDEF101015121287665 （a）无向网）无向网G1算法演示算法演示:Prim算法求解最小生成树算法求解最小生成树CE1015765（b）求解过程）求解过程ABCDEF101015121287665 （a）无向网）无向网G1算法演示算法演示:Prim算法求解最小生成树算法求解最小生成树CE1015765

20、（b）求解过程）求解过程86ABCDEF101015121287665 （a）无向网）无向网G1算法演示算法演示:Prim算法求解最小生成树算法求解最小生成树CE10101575（b）求解过程）求解过程6ABCDEF101015121287665 （a）无向网）无向网G1算法演示算法演示:Prim算法求解最小生成树算法求解最小生成树E101075（b）求解过程）求解过程1567ABCDEF101015121287665 （a）无向网）无向网G1算法演示算法演示:Prim算法求解最小生成树算法求解最小生成树E1010125（b）求解过程）求解过程67ABCDEF101015121287665 （

21、a）无向网）无向网G1算法演示算法演示:Prim算法求解最小生成树算法求解最小生成树最小生成树最小生成树E10105最小生成树最小生成树不唯一！不唯一！例1654326513566425131163141643142116432142516543214253普里姆算法普里姆算法7.4.2 克鲁斯卡尔算法（克鲁斯卡尔算法（Kruskal）算法思想：假设连通网算法思想：假设连通网 N=（V，E），则令最小），则令最小生成树的生成树的初始状态为只有初始状态为只有n个顶点而无边的非连通图个顶点而无边的非连通图T=（V，E1），）， 其中其中E1为空集，即为空集，即T中的每个顶点自中的每个顶点自成一个连

22、通分量。在成一个连通分量。在E中中选择权最小的边选择权最小的边，若该边依若该边依附的顶点落在附的顶点落在T中不同的分量上中不同的分量上，则将此边加入到，则将此边加入到T中，中，否则舍去此边选择下一条权最小的边。依次类推，直否则舍去此边选择下一条权最小的边。依次类推，直到到T中所有顶点都在同一连通分量上。中所有顶点都在同一连通分量上。克鲁斯卡尔算法克鲁斯卡尔算法abcdegf195141827178213127【练习】【练习】利用利用Prim算法求最小生成树算法求最小生成树权和权和= 14+8+3+5+17+21 = 68利用利用Kruskal算法求最小生成树算法求最小生成树【练习】请分别用【练

23、习】请分别用Prim算法和算法和Kruskal算法构造以算法构造以下网络的最小生成树。下网络的最小生成树。3V0V1V3V5V4V221332【Prim算法】算法】V0V1V3V5V4V221332【Kruskal算法】算法】练习练习请使用克鲁斯卡尔算法请使用克鲁斯卡尔算法( Kruskal )求下图的最小生成树。求下图的最小生成树。 在日常生活中，我们如果需要常常往返于在日常生活中，我们如果需要常常往返于A A城市和城市和B B城市，我们最希望知道的可能是从城市，我们最希望知道的可能是从A A城市到城市到B B城市间众多路径中，那一条最短城市间众多路径中，那一条最短的路径。的路径。最短路径最

24、短路径是指所经过的边上的是指所经过的边上的权值之和为最权值之和为最小小的路径，而不是经过的边的数目为最少。的路径，而不是经过的边的数目为最少。最短路径问题有两个算法最短路径问题有两个算法:一个是求从某个源一个是求从某个源点到其他各顶点的最短路径的点到其他各顶点的最短路径的迪杰斯特拉迪杰斯特拉（Dijkstra）算法。）算法。7.5.1 从某个源点到其他各顶点的最短路径从某个源点到其他各顶点的最短路径算法思想：算法思想：按按最短路径的长度最短路径的长度递增的次序求递增的次序求得各条路径。得各条路径。最短路径问题 DijkstraDijkstra的算法的算法 算法描述算法描述l 将起始定点插入树中

25、；将起始定点插入树中；l 找出树中所有顶点的邻接边中总和最小的边；找出树中所有顶点的邻接边中总和最小的边；l 重复第二步骤，直到所有的顶点都在树中为重复第二步骤，直到所有的顶点都在树中为止。止。4最短路径问题 实例实例1 找出从城市找出从城市A到其他所有城市的最短路径到其他所有城市的最短路径2BACDEF36253435BACDEF3233W=6W=3最短路径问题 2BACDEF36253435BACDEF36步骤步骤1：从城市A出发，找出和A邻近且有路径的城市，B和C。我们用W表示路径总和路径总和。234W=5W=6W=3最短路径问题 2BACDEF36253435BACDEF36步骤步骤2

26、：从总和路径最小总和路径最小的C出发,找出与C邻近的路径,CB,CD和CE。W=6W=7最短路径问题 此时我们发现此时我们发现,从从A经过经过C到达到达B的总和路的总和路径为径为5,比从比从A直接到直接到B的路径总和路径的路径总和路径(6)小小.因此因此,我们选择从我们选择从A经过经过C到到B,这条路径这条路径.234W=5W=6W=3BACDEF36W=6W=7234W=5W=3BACDEF3W=6W=75W=10W=6234W=5W=3BACDEF3W=7 最短路径问题 2BACDEF36253435步骤步骤3：接下来从总和路径比C大且最接近C的B出发,我们找出与城市B邻近的路径,有BD。

27、W=10W=6234W=5W=3BACDEF3W=7最短路径问题 此时我们发现此时我们发现,从从C经过经过B到达到达D的总和路径的总和路径为为10,比从比从C直接到直接到D的路径总和路径的路径总和路径(6)大大.因此因此,我们选择从我们选择从C直接到直接到D的路径的路径.234W=5W=3BACDEF3W=6W=75W=9W=6234W=5W=3BACDEF3W=72W=83最短路径问题 2BACDEF36253435步骤步骤4：接下来我们从总和路径比B大且最接近B的D城市找,我们找出和城市D邻近的路径,有DE,DF。W=9W=6234W=5W=3BACDEF3W=72W=83 最短路径问题

28、此时我们发现此时我们发现,从从C到达到达E的总和路径为的总和路径为7,比比从从D到达到达E的总和路径的总和路径(8)小小.因此因此,我们选择我们选择从从C直接到直接到E的路径的路径.W=9W=6234W=5W=3BACDEF3W=735最短路径问题 2BACDEF36253435步骤步骤4：接下来我们从总和路径比D大且最接近D的E城市找,有EF。W=12W=7W=9W=6234W=5W=3BACDEF335W=12W=7W=9W=6234W=5W=3BACDEF33最短路径问题 此时我们发现此时我们发现,从从D到达到达F的总和路径为的总和路径为9,比比从从E到达到达F的总和路径的总和路径(12)小小.因此因此,我们选我们选择从择从D直接到直接到F的路径的路径.W=9W=6234W=5W=3BACDEF3W=73最短路径问题 从右图我们可以看出从右图我们可以看出: 从城市从城市A A到到B B的最短