数据结构与算法（Java语言版）课件 第13、14章 图论、经典算法思想

第13章图论2024/11/912024/11/92

13.1无向图2024/11/93

⒈无向图的定义2024/11/9413.1无向图

⒈无向图的定义2024/11/9513.1无向图

2邻接点

2024/11/9613.1无向图3.路径

2024/11/9713.1无向图4.连通图

13.2有向图2024/11/98⒈有向图的定义

2024/11/9913.2有向图

⒈有向图的定义

2024/11/91013.2有向图2邻接点

2024/11/91113.2无向图3.路径

2024/11/91213.2有向图4.强连通图

13.3网络2024/11/913

2024/11/91413.3网络刻画北京，广州，成都和上海四个城市之间的民航航线，航线之间的权重是航线距离。2024/11/91513.3网络刻画北京，广州，成都和上海四个城市之间的民航航线，航线之间的权重是航线的票价（往返的票价不尽相同）。13.4图的存储2024/11/9161.邻接矩阵

13.4图的存储2024/11/9171.邻接矩阵

2024/11/91813.4图的存储例子1Example13_1.javaGraphByMatrix.java例子1中的GraphByMatrix类使用邻接矩阵存储图或网络的边。例子1的主类Example13_1使用GraphByMatrix类演示了无向图、有向图和有向网络使用邻接矩阵存储边.13.4图的存储2024/11/9191.邻接表

2024/11/92013.4图的存储例子2Example13_2.javaGraphByLinkedList.java例子2中的GraphByLinkedList类使用邻接链表存储图或网络的边。例子2的主类Example13_2使用GraphByLinkedList类演示了无向图、有向图和有向网络使用邻接链表存储边.13.4图的遍历2024/11/921

13.4图的遍历2024/11/922广度搜索（BFS）则是从起点开始，逐层访问所有路径可达到的顶点，一层一层地往外扩展（广度优先），直到所有路径可达到的顶点都被访问到，就结束此次遍历过程。如果图中仍然有没访问过的顶点，就在没访问过的顶点中，选择一个顶点重新开始遍历。广度优先搜索一直到图中再也没有可访问的顶点，就结束搜索过程。广度优先搜索的算法中可以用队列（Deque）这种数据结构体现广度优先.2024/11/92313.5图的遍历例子3Example13_3.javaGraphDFS.java1.深度优先搜索（DFS）算法DFS算法描述如下。①检查是否已经访问了全部的顶点，如果已经访问了全部的顶点，进行③，否则，将一个不曾访问的顶点压入栈，进行②。②如果栈是空，进行①，否则进行弹栈，把弹出的顶点标记为访问过的顶点，然后把弹出的顶点的邻接顶点压入栈（体现深度优先），但不再对访问过的顶点进行压栈操作，再进行②。③算法结束。例子3中的GraphDFS类封装了DFS算法。Vertex.java2024/11/92413.5图的遍历例子4Example13_4.javaGraphBFS.java2.广度优先搜索（BFS）算法例子4中的GraphBFS类封装了BFS算法。Vertex.javaBFS算法描述如下：①检查是否已经访问了全部的顶点，如果已经访问了全部的顶点，进行③，否则，将一个不曾访问的顶点入列，进行②。②如果队列是空，进行①，否则进行出列操作，把出列的顶点标记为访问过的顶点，然后把出列的顶点的邻接顶点入列（体现广度优先），但不再对访问过的顶点进行入列操作，再进行②。③算法结束。13.6测试连通性2024/11/925从任意顶点开始遍历图中的顶点，方法结束后，使得图的顶点都可以被访问了一次，那么该图就是连通图或强连通图。如果存在某个顶点vertex，使得graphBFS(vertex)或graphDFS(vertex)执行完毕后，图中还有某些顶点未被访问，那就说明顶点vertex和这些未被访问顶点之间没有路径相连接，因此，图就不是连通图。2024/11/92613.6测试图的连通性例子5Example13_5.javaTestConnection.java例子5中的TestConnection类的isConnection(GraphDFSgraph)方法和isConnection(GraphBFSgraph)方法，分别借助例子3和例子4中的GraphDFS类和GraphBFS中的深度优先搜索（graphDFS(Vertexvertex)）和广度优先搜索（graphBFS(Vertexvertex)）测试图graph是否是连通图。13.7最短路径2024/11/927

13.7最短路径2024/11/928

13.7最短路径2024/11/929

13.7最短路径2024/11/930

13.7最短路径2024/11/9312024/11/93213.7最短路径取第0个顶点，第1次迭代得到：2024/11/93313.7最短路径取第1个顶点，第2次迭代得到：2024/11/93413.7最短路径取第2个顶点，第3次迭代得到：2024/11/93513.7最短路径取第3个顶点，第4次迭代得到：2024/11/93613.7最短路径取第3个顶点，第4次迭代得到：2024/11/93713.7最短路径

2024/11/93813.7最短路径例子6Example13_6.javaFloyd.java例子6中的Floyd类的floyd(int[][]graph)方法是经典的Floyd最短路径算法。13.8最小生成树2024/11/939

13.8最小生成树2024/11/940一个网络的可能有很多生成树，人们关心的往往是最小生成树。最小生成树是生成树中边的权值总和最小的某个生成树（可能有多个生成树的权值总和相同，同时也是最小之一）。如果网络中的权值互不相同，那么最小生成树一定是唯一的。13.8最小生成树2024/11/941Prim给出MST算法（1957年由美国计算机科学家普里姆独立发现），称作Prim算法。该算法可以从网络的任何一个顶点开始，得到最小生成树。2024/11/94213.8最小生成树

2024/11/94313.8最小生成树例子7Example13_7.javaGraphMTS.java例子7中的GraphMTS类的mitPrim(int[][]graph)方法是经典的Prim算法。Edge.java

第14章经典算法思想2024/11/944主要内容贪心算法

动态规划回溯算法2024/11/945经典算法思想是经过长时间的实践积累，总结出的算法思想。通过运用经典算法思想去分析问题，采用抽象的数学模型来描述问题，然后再使用算法进行求解，能够提高算法的效率和解决问题的质量。很多重要的具有特色算法都是在经典算法思想的基础上发展起来的，例如深度学习中的神经网络就是基于动态规划和优化的思想而发展起来的。总之，经典算法思想的重要性不仅在于它们被广泛应用于解决实际问题，更重要的是这些思想具有一定的普适性和通用性，是学习算法设计者必须要了解和掌握的。2024/11/946本章讲解贪心算法、动态规划和回溯算法这三种经典算法思想，这些算法思想和普通的具体的算法，比如起泡排序、二分法、遍历二叉树等算法不同，这些算法思想不会给出具体的代码流程，仅仅是提供一种算法的设计思想或解决问题的算法思路，这些算法思想应用在不同的具体问题里，所呈现的具体代码可能有很大的差异。。14.1贪心算法2024/11/947⒈贪心算法贪心算法（也称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。即不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择。也就是说，不从整体最优上加以考虑，做出的只是在某种意义上的局部最优解。贪心算法的特点是一步一步地进行，以当前情况为基础，根据某个算法作最优选择，而不考虑各种可能的整体情况，通过每一步贪心选择，可得到局部最优解。由于贪心算法每一步是局部最优解，因此，如果使用贪心算法，必须要判断是否得到了最优解。14.1贪心算法2024/11/948⒈贪心算法例如，蒙眼爬山，蒙眼爬山者选择的策略是每次在周围选择一个最陡峭的方向爬行1小步（局部最优选择），但是蒙眼爬山者最后爬上去的山可能不是最高的山（爬山者周围是多峰山），假设蒙眼爬山者携带了一个自动通报海拔高度的小仪器，每次都报告海拔高度，当蒙眼爬山者发现周围没有陡峭的方向可走了，报告海拔高度恰好是想要的高度，那就找到了最优解，否则就知道自己旋入了局部最优解，无法继续下去了。贪心算法仅仅是一种思想而已，不像我们熟悉的选择法排序、二分法等算法有明确的算法步骤。2024/11/94914.1贪心算法2老鼠走迷宫贪心策略如下（这里称二维数组元素为路点，其值为路值）。①如果当前路点不是出口（最大值），即不是最优解，就降低优先度，将当前路值减1，进行②，如果当前路点是出口（最大值）进行④。②在当前路点的东西南北方向选出路值比当前路值大的最大新路点，如果找到进行③，否则回到①。③老鼠达到选出的新路点，进行①。④结束。如果路点的路值不会被减到等于墙的值(Long.MIN_VALUE)，就一定能到达出口，否则某个路点或墙会被当成出口（因为Long.MIN_VALUE-1等于Long.MAX_VALUE，老鼠陷入局部最优解）。2024/11/95014.1贪心算法2老鼠走迷宫例子1Example14_1.javaMouse.java例子1的Moues类中的walkMaze()方法使用了贪心算法。14.2动态规划2024/11/951⒈动态规划

2024/11/95214.2动态规划2.0-1背包问题

0-1背包问题中的价值和重量仅仅是问题的一种描述形式，对于某些实际问题，重量可能是体积等其它单位，比如，集装箱装载货物的0-1背包问题，可能用体积代替重量。2024/11/95314.2动态规划2.0-1背包问题

0-1背包是背包问题中最简单的问题，动态规划的思想很适合用于解决0-1背包问题。2024/11/95414.2动态规划2.0-1背包问题0-1背包是背包问题中最简单的问题，动态规划的思想很适合用于解决0-1背包问题。

2024/11/95514.2动态规划2.0-1背包问题0-1背包是背包问题中最简单的问题，动态规划的思想很适合用于解决0-1背包问题。

2024/11/95614.2动态规划2.0-1背包问题例子2Example14_2.javaKnapsack.java例子2中的Knapsack类的DP()方法是背包算法.例子1的主类Example14_2使用Knapsack类的DP()方法解决了下列两个背包问题.①背包最多可以载量8kg的物品，现在有重量依次为2,4,5,1（单位是kg）的4件物品，对应的价值依次为7,6,8,2（单位是￥）。怎样让背包中放置的物品价值最大？②学生选课时限制总学时为100个学时，现有5门选修课，这5门选修课的学时依次为20,20,60,40,50。对于5门选修课中的每门课程，学生修完该课程对应的全部学时才能得到这门课程的学分（要么不选，选了就必须完成课程规定的学时），这5门课程对应的学分依次为6,3,5,4,6。怎样选课可以让学分最多？2024/11/95714.2动态规划3.优化0-1背包问题例子3Example14_3.javaKnapsackOptimize.java对于许多实际问题，对应的DP-方程中有许多子问题可能是重叠的子问题，因此需要使用动态规划的思想进行优化处理，避免多次计算子问题的解。例子3中的KnapsackOptimize类中的DP()方法是优化的DP-方程。例子3的主类Example14_3解决规模较大0-1背包问题（物品的数量较大）。比较了例子2中的Knapsack类的DP()方法和例子3中KnapsackOptimize类中的DP()方法在解决同一背包问题的运行耗时.14.3回溯算法2024/11/958⒈回溯算法回溯算法又称为试探算法，是一种算法思想，其核心思想是不断地按某种条件求“中间解”来寻找“目标解”，但当进行到某一步时，也称为达到一个“搜索点”时，发现已经无法按既定条件继续求“中间解”时，即无法在此搜索点达到下一个搜索点，就要进行回退操作，这种算法无法进行下去就回退的思想为回溯算法，而满足回溯条件的某个状态的点称为“回溯点”。14.3回溯算法2024/11/959⒈回溯算法

14.3回溯算法2024/11/9602九宫格九宫格游戏是在一个3×3方格中放有1至8的数字、剩下一格为空白。先设定1至8的初始排列状态，然后开始不断的移动空白（空白周围的数字可移至空白，相当于移动空白）的位置