大连专业手机自适应网站建设维护,做网站客户一般会问什么问题,点餐小程序模板,重庆网票app下载文章目录 图1.图的两种存储结构2.图的两种遍历方式3.最小生成树的两种算法#xff08;无向连通图一定有最小生成树#xff09;4.单源最短路径的两种算法5.多源最短路径 图
1.图的两种存储结构
1. 图这种数据结构相信大家都不陌生#xff0c;实际上图就是另一种多叉树… 文章目录 图1.图的两种存储结构2.图的两种遍历方式3.最小生成树的两种算法无向连通图一定有最小生成树4.单源最短路径的两种算法5.多源最短路径 图
1.图的两种存储结构
1. 图这种数据结构相信大家都不陌生实际上图就是另一种多叉树每一个结点都可以向外延伸许多个分支去连接其他的多个结点而在计算机中表示图其实很简单只需要存储图的各个结点和结点之间的联系即可表示一个图顶点可以采取数组vector存储那顶点和顶点之间的关系该如何存储呢其实有两种方式可以存储顶点与顶点之间的关系一种就是利用二维矩阵(二维数组)某一个点和其他另外所有点的连接关系和权值都可以通过二维矩阵来存储另一种就是邻接表类似于哈希表的存储方式数组中存储每一个顶点每个顶点下面挂着一个个的结点也就是一个链表链表中存储着与该结点直接相连的所有其他顶点这样的方式也可以存储结点间的关系。
2. 图还可以细分为无向图和有向图其实很好区分如果AB两个点之间的连线是无向的那就默认代表A可以到达BB也可以到达A那这样的图就是无向图如果AB两个点之间的连线是有向的比如A指向B那就代表只能A到达B不能B到达A。每两个点之间的连线还可以加权你可以将他理解为是通过该线到达对方所需要花费的驾驶成本。 其实图还有很多其他的概念例如子图连通图强连通图最小生成树有向完全图无向完全图等等但这些概念网上一搜你就知道是什么所以这里不会再继续聊这些无聊的概念了直接上图这种数据结构的相关代码
3. 下面代码是用邻接表来实现的图主要成员变量就是一个vector来存储所有的顶点另一个类似于哈希表的邻接表来存储某一个顶点与其他所有顶点之间的关系还需要一个哈希表的原因是因为我们需要拿到结点对应的下标在图当中结点的类型是不确定的可能是stringdoublefloat还有可能是自定义类型所以我们需要vector来存储这些不确定类型的结点而在vector里每个结点就会和数组的下标索引关联上了存储结点之间的关系时我们都是通过操作结点对应的下标来对图进行关系的增查改的所以为了提高找到结点对应的下标索引我们额外用一个哈希表来存储结点和索引的键值对关系。 构造函数需要外部传入一个顶点数组的指针以及顶点的个数通过这两个参数我们就可以确定好_vertexes和_index存储的内容了。 添加边关系的接口也会提供给外部如果图是无向图则可以外部指定边的默认权值为-1或者是0等等由使用者来定义。 邻接表的每个顶点由后继指针顶点下标权值三部分组成。 4. 邻接矩阵来实现图其实要方便许多添加顶点之间的关系时只需要更改矩阵中对应位置存储的值即可而无需向邻接表似的还需要额外添加顶点不过邻接矩阵和邻接表相比各有优劣对于稠密图也就是图中边的数量很多这种图就适合用邻接矩阵来存储因为不管图是稠密还是稀疏邻接矩阵空间大小都不变那存储稠密图相对稀疏图空间利用率就会高很多对于稀疏图就适合用邻接表来存储因为边的数量较少用占有空间率较大的邻接矩阵来存储就不太划算而邻接表可能只需要添加那么几个顶点就可以完成图的构建这样就会划算很多。但邻接矩阵的好处就是可以快速判断两个点是否相连而邻接表如果想要判断就需要遍历一串链表但当判断某一个点向外连接了哪些顶点时邻接矩阵的效率就相对低了因为他要遍历二维矩阵的一整行来判断时间复杂度就是O(N)而对于邻接表只需要遍历常数次的链表结点即可效率相对要高一些但如果要实现后面的算法比如图的bfs和dfs遍历kruskalprimdijkstralbellman-fordfloyd-warshall经常需要拿到两个点相连边的权值如果是邻接表的话就需要对结点指针解引用拿到权值我感觉是比较麻烦的同时遍历某一个顶点向外与哪些顶点相连时邻接表需要遍历链表那就需要while循环来遍历用邻接表也不是不行但是邻接矩阵用起来比较符合大部分人的图使用习惯所以后面实现的算法都是用邻接矩阵来实现的。 下面邻接矩阵的代码中的接口和临界表的实现大差不差邻接矩阵中存储值我们可以将其初始化为INT_MAX添加顶点之间的关系时其实就是对邻接矩阵中存储的值做改动而已。 所以实现图这种数据结构并不困难难的是实现图相关的算法。 2.图的两种遍历方式
1. 关于dfs和bfs这两种遍历方式相信大家是不陌生的深度优先遍历需要借助函数栈帧也就是函数的递归调用来实现不断的向深处递归满足某一条件时递归结束开始回溯往回走广度优先遍历需要借助队列因为每遍历某层的某个数据元素为了让他所连接的下一层在下次也能够遍历到那就需要按照FIFO的方式将他下一层相连的元素push到data structure中这种访问方式刚好就是队列这种数据结构的特性。
2. 对于下面图的bfs来说当我们访问完A之后我们想按照顺序访问BCD因为与A直接相连的只有BCD假设我们访问完BCD那么按照顺序来说下一次就应该访问与B直接相连的E但此时就有细节需要注意了因为与B直接相连的不仅仅只有E还有访问过的A和C所以在push与当前结点直接相连的下一层的元素时需要保证已经访问过的结点不要再次push到队列里面。可以通过一个visited[bool]数组来完成这个细节的处理对于已经访问过的结点数组里面对应位置存储的值就是true没有访问过的结点就是false。 代码实现的方式较为简单每次在pop队头同时访问完毕元素之后都会把与元素直接相连的其他未访问过的结点尾插到队列里面我们只需要不断while循环的访问队列中的元素直到队列为空就可以实现图的bfs方式的访问这里面有一点实现上的细节就是关于visited数组的modify下面实现的代码是将当前元素相连的下一层所有元素尾插的同时标记visited数组为true这样其实是没问题的想法就是只要在队列里面待着的元素那迟早是要被访问的所以只要元素一入队列那就直接将该元素在visited中的位置写为true即可。另一种想法就是我不着急一下子就把下一层的元素全写为true而是每次刚拿出队头的元素时我再单独将这个元素写为true那在push下一层结点时依旧不会影响当前这一层元素误被再一次push到队列中两种更改visited数组的想法均可以看个人习惯实现即可。 3. dfs算是一个算法入门程序员的基本功了回溯算法其实就是在递归的基础上延申出来的所以学好递归对于学习算法其实是很重要的。实现dfs与bfs同样都有一个点需要注意在bfs那里尾插下一层结点时需要防止当前层的结点重复尾插到队列中因为我们不希望已经被访问过的结点再次被访。而在dfs这里当我们递归到最深时也就是当前结点不再和其他任何结点相连时代表这一趟的搜索其实已经完成了那么此时递归就要结束了因为递归条件已经不满足了有人可能会问递归条件是什么呢递归条件其实就是只要当前结点直接相连的结点个数不为0那就继续向深处进行遍历当结点个数为0时那自然递归就结束了。而此时回溯的时候就出现问题了上一层已经访问过的结点我们还要再访问吗当然不要所以在dfs这里依旧需要一个visited数组来标记已经访问过的结点防止递归在回溯时重复访问已经访问过的结点。 注意我实现的其实是Graph类的成员函数如果是在OJ题里面的话visited数组肯定是要设置成全局的 3.最小生成树的两种算法无向连通图一定有最小生成树
1. 最小生成树通常针对的其实是无向连通图而求解最小生成树已知的两种算法是kruskal和prim算法理解完两种算法的思想和实现方式之后再来讨论为什么最小生成树通常针对于无向连通图如果应用到有向连通图上呢得到的还是最小生成树吗 最小生成树其实就是将图中的所有顶点通过边连通起来我们当然可以选择任意条不超过图中边总数的边来将各个顶点连接起来但最小生成树指的是在无向连通图中选择顶点个数-1条边将所有顶点连接起来同时这些边的权值之和是连通所有顶点需要边的权值之和中最小的而连接起来的顶点你将其从图中抽离出来画到另外一张纸上经过形状的调整他其实就是一棵树这棵树就叫做最小生成树。有人可能会有疑问为什么边的数量是n-1条呢因为连接n个顶点需要的最少的边就是n-1条如果边的数量超过了n-1条那么挑选的边就必然会形成环超出n-1条的边一定是多余的这样权值之和一定是小于n-1条边的所以这样肯定不是最小生成树。 为什么在最小生成树这里不断的强调是连通图呢(先不谈是有向还是无向)因为如果不是连通图顶点是一定没有办法通过边来连通起来的一定会有顶点是孤立的岛所以最小生成树算法的使用前提是连通图必须是连通图通常是用于无向的连通图有向连通图也可以使用但这里先不谈了解完prim和kruskal之后再继续谈。
2. 我大概在2023年的10月份系统学过一个月左右的各个算法有难有简单其中比较特殊的算法就是贪心算法能想出来这种算法的人基本已经青史留名了而作为后代的我们其实只要做到脑中理解这种算法或者是能感受到这种算法的确是正确的就可以了反正我自己是这么觉得的而证明贪心算法的正确性是真的要有不错的数学基础但按照本人的这个算法和数学功底来看我是没能力证明算法的正确性的同时在学图这块的算法时有一说一我想让我的大脑尽量理解这种算法是正确的让我的大脑相信这种贪心算法一定是能够考虑到各种特殊情况最终得到正确答案的这一事实都是比较困难的当时让大脑相信这种正确性其实是花费了不少时间的也有可能是我这个脑子比较笨不去做证明仅仅让大脑尽量去理解这种贪心算法的正确性都很吃力所以下面涉及到所有的贪心算法只会讲本人对其正确性的理解而不会谈论证明他的正确性因为你让我讲我也讲不了本人太菜了啊。 kruskal算法的本质是贪心算法在上面了解最小生成树的概念之后你其实会发现求解最小生成树过程的核心工作其实就是挑选边在一个无向连通图中所有的边中挑选出来n-1条权值之和最小的边而kruskal和prim算法的不同其实就是选边策略的不同但他们最后都能求出来最小生成树。选边的策略其实就是kruskal和prim作为贪心算法的实际贪心策略通过合理的贪心策略最终解决问题。 kruskal的贪心策略其实是比较好理解的他是一种全局站在上帝视角的贪心对于图中所有的边我们从小到大进行挑选每次挑选边都必须保证不能形成环因为我们知道只要形成环那其实就代表挑选出来的这条边是多余的边因为即使没有这条边也不会影响已经连接在一起的结点的连通性所以在挑选边的过程中不可以形成环同时必须从小到大的一直挑选边直到挑选出n-1条边当然如果图不是连通图那我们怎么也无法挑选出能够组成最小生成树的边出来对于这种特殊情况需要在写代码时特殊注意一下。 总结一下kruskal从上帝视角来看每次挑选的边都是最优的同时防止形成环(防止不必要的边的选入)那么最后挑选出来的边的总和一定也是最小的这样就可以求出最小生成树。 3. 在kruskal挑选边中我们需要从小到大的挑选边可以通过数组排序的方式来从小到大依次拿取边也可以通过优先级队列也就是堆的方式来实现建立一个小堆将图中所有的边push到小堆里面依次拿出堆顶的元素就是从小到大拿取边还有一个需要解决的问题就是如何判环其实这个步骤需要通过并查集来解决并查集刚好可以用来判断两个结点是否在同一集合当中对于挑选出来的边我们可以判断挑选边所连接的两个顶点是否在同一集合当中如果在那就说明挑选出来的边会形成环如果不在那就说明挑选出来的边是有效的是可以连通这两个顶点的。
4. prim是局部的贪心来挑选边并不像kruskal一样站在全局上帝的视角来挑选边他的策略是从已经选择的点向外连接的所有边中挑选一个最短的边。例如图a假设从a顶点开始向外挑选只有4和8两条边则优先选择4这条边因为这一步一定是最优的对于想要从a向外连接其他顶点来说下一步对于ab两个顶点向外连接的所有边中再次选择最小的边不断向外选择直到连接完毕所有的顶点。需要说明的是prim的思想其实是把图中的顶点分为两类一类是已经选择好的另一类是未选择的每次挑选边都是从已选择的顶点出发到未选择的顶点看哪条边最小就选择那条边虽然思想是这样的但如果按照这个思想实现代码的话其实选边的过程是非常头疼的因为每次选边都需要依次遍历已选择的顶点集合中所有的点将每个点作为起点连接到未选择的顶点集合中的所有点相当于要遍历m×n次m和n分别代表两个集合的顶点个数等到选择一半的时候m和n就会相等变为顶点集合总数的一半那相乘之后的选边时间复杂度就会达到O(N²)无疑这样的选边效率太低所以我们不用来回遍历的这种方式选边而是依旧使用优先级队列来选边。 但在prim这里用优先级队列有可能产生环因为在局部不断选边的过程中有些无效边会滞留到小堆里面我们无法做到将具体的某个无效边从小堆里面删除所以为了解决环的问题实现prim时依旧需要使用并查集来判环。下面算法导论给出的例子中如果使用优先级队列选择当前顶点向外连接的所有边中的最小边不断不断选的过程中会在c i g f这里形成环 5. 当prim和kruskal用于有向连通图时求出来的就不是最小生成树了而是最小生成森林kruskal在选边时由于全局选边的特性实际上是无视边的方向的所以最终选出来的可能是拥有多个根节点的最小生成森林而prim在局部选边时就比较麻烦了因为随机的某个出发点可能没有出度只有入度那么出发点就无法到达其他顶点这样出发点就单独是一棵树接下来如果要继续选边那就需要看代码的具体实现了每个人都可以实现的不同例如接下来随机或者轮询的选择某一个未确定的顶点作为新的出发点然后继续向后选边实现起来可能稍微要比无向连通图麻烦一些。 我们这里也是思维跳跃的想了想有向连通图下prim和kruskal的实现但大部分情况下你从网上搜没人会实现有向连通图下的这两种算法95%的情况都是针对于无向连通图来求最小生成树进行使用。
4.单源最短路径的两种算法
1. 单源最短路径指的是选择一个出发点从这个出发点到其他所有顶点的最短路径是什么dijkstra和bellman-ford可以求出单源最短路径但dijkstra只适用于权值为正的图不能适用于携带负权值的图bellman-ford可以适用于携带负权值的图但对于携带负权环的图bellman-ford也无法解决最短路径问题了只能判断出该图存在负权环。dijkstra的算法时间复杂度最坏情况就是O(N²)bellman-ford算法的时间复杂度最坏情况是O(N三次方)实际上dijkstra是贪心算法而bellman-ford算法是暴力循环遍历这也是为什么dijkstra算法效率高的原因。 在谈论两种算法之前还需要补充一个前置知识松弛更新松弛操作其实很好理解拿下面的图举例子在逻辑上每个结点中存储一个权值该权值其实就是从出发点到该点的最短路径上路径的权值之和但刚开始时所有结点中存储的值应该都是∞而所谓的松弛操作就是指从当前结点出发到直接相连的下一个结点如果当前结点上的权值加上路径的权值小于下一个节点存储的权值那么此时我们进行下一个结点存储值的松弛更新操作将其权值之和更新为更小的值。 所以总结一下所谓的松弛操作就是指从某一结点出发到下一个结点如果路径权值当前结点权值之和更小那就将这个更小的值更新为下一个节点存储的值这就代表从出发点到这个新顶点有了一条更短路径。如果这里看懂有点迷糊也正常说的都是我自己的理解可以直接去看下面的dijkstra的例子这样你就很好理解松弛操作了他其实就是一个更新权值的操作而已
2. 刚开始除了s自己是0之外其他结点都是无穷大因为s到s自己的路径权值不需要更新默认为0即可然后松弛更新与s直接相连的t和y结点因为10和5均各自小于无穷大所以可以更新权值下一步就是挑选下一个出发点作为新的起始点挑选下一个顶点的策略其实就是dijkstra的贪心策略了由于5比10小所以y存储的值就是从出发点s到y的最短路径没有其他路径能够比当前这个路径更优了所以y是第一个已经确定最短路径的顶点有人会有疑问凭什么y就已经确定了最短路径呢 dijkstra适用的图都是权值均为正数的图那可以想一下s到y只有两种情况一种是直接到达y另一种是通过其他路径本图中是通过t绕一圈可能到达y这两种到y的方式一定是前者更优因为在s第一次松弛更新时t和y存储的值相比y就是最小的值了如果按照后者的方式s第一步到t此时的权值就已经大于y了何况你还要从t作为出发点再继续绕一圈到y那最后累积的权值一定是要比s直接到y要小的因为只要你从t向外绕路上途径的任何一条边的权值都是正数那权值就一定会累加所以以s作为起点松弛更新之后我们就可以拿到一个新的已经确定好最短路径的新的起点了那就是y。 接下来道理相同以y作为新起点继续向外松弛更新那txz三个顶点存储的值都会被更新此时选择下一个新的起点该如何选择呢其实还是一样的我们依旧选择txz三个顶点中存储值最小的点z作为新起点有人感受这个地方可能觉得还是别扭的不行别扭还是没抓住关键关键就是我们每次选择下一个顶点时选择的都是权值最小的顶点这样有什么好处呢如果我们选择t或x作为新顶点能不能到达z呢肯定是可以的但有意义吗当然是没有意义的因为t和x本身的权值都已经大于z的权值了那从t和x出发能找到到达z的最短路径吗一定是找不到的只有选择当前已经更新的结点中存储权值最小的顶点作为新起点才是最优的选择因为他存储的值其实就已经确定好了最短路径了。 我说了这么多不知道你理解没有核心就是每次选择下一个权值最小的顶点作为新起点这样一定是最优的你想嘛你选的都是最小权值的了其他顶点都比你大那他们绕一圈肯定还是比你大那你当前的存储权值所对应的路径其实就已经是最短路径了因为没有比你更优的选择了这样贪心的策略就是dijkstra算法 3. 在代码实现上要考虑的细节是比较多的我们肯定不可能向图中的逻辑表示一样给每个结点做一层封装让结点中存储一个权值之和这样无疑是比较繁琐的其实完全可以用一个int数组shortPath来解决数组的下标对应着每个结点下标中存储的值就是从出发点到该点的最短路径上的权值之和解决完最短路径的权值之和后还有一个问题要解决我们需要能够表示出来这条最短路径知道路径上都通过了哪些结点这个问题该如何解决呢需要用到一个prev数组prev数组的下标依旧对应每个顶点存储的值表示前一个结点的下标如果想要拿到完整的最短路径则可以不断根据索引访问prev数组依次拿到前一个结点的下标直到回溯到最开始的出发点为止。 在松弛更新时已经确定最短路径的结点实际上是不需要在更新了所以我们可以再额外搞一个confirm标记数组来标记已经被确定好最短路径的结点在向外松弛更新时不处理这些结点。 在理解dijkstra的贪心策略以及实现时上面的需要注意的点实现代码并不困难具体可看代码截图 4. 当图中存在了负权边时dijkstra的贪心策略就无法使用了道理很简单如果我们还按照原来的策略进行选边的话第一步就会出问题拿下图这个bellman-ford算法执行过程举例的话第一步s先将t和y分别更新为6和7此时能因为t的权值6小于y的权值7就说t已经确定了最短路径吗这里的第一步贪心就会出错因为虽然y现在的权值大于t但由于图中存在负权边那就可能存在一种情况也就是从y绕出去最后绕到t绕一圈之后的权值之和是可能小于6的所以6并不一定是最短路径也就是说我们的贪心策略失效了不能用这种取巧的方法来求解单源最短路径了那该怎么办呢 解决的思想很简单就是直接暴力遍历以所有的顶点为起点去向外松弛更新遍历一圈顶点每个顶点都松弛更新一遍这样算是完成一次循环最多需要完成n(顶点个数) - 1次循环即可得出所有顶点的最短路径我上面简单叙述的过程就是bellman-ford的算法思想思想说起来可能很简单但确实不太好理解所以下面为大家准备了两张示例图一张是我自己画的图一张是算法导论上面的推荐先看我画的图然后再看算法导论上面的图因为算法导论总结的比较精炼和抽象没那么容易读懂。 在bellman-ford这里经典的一个疑问就是为什么最多要遍历n-1次循环因为求解一条最短路径这条最短路径最长也就是n-1条边组成的bellman-ford每次循环最少最少都能够确定出这条最短路径的一条边出来所以最坏的情况下假设每次bellman-ford只能确定出某个顶点的最短路径上的一条边那么经过n-1次循环后也就能够求出最短路径的权值之和了。 如果情况比较好的话向下图所示只需要经历4次循环我们发现第三次和第四次结果没有发生变化那就不需要继续经历循环因为最短路径已经求解出来了那就可以提前跳出循环。 总结bellman-ford的算法思想就是以所有的顶点为起点向外松弛更新至多循环n-1次即可求出所有顶点的单源最短路径 遍历顶点的顺序可以变但不管怎么变bellman-ford都是可以求出来最短路径的 5. 在实现代码时需要额外判断的就是负权环因为当图中存在负权环时无论你继续暴力循环遍历多少次遍历无数次都一样每一次仍然能够进行松弛更新操作因为只要有负权环以某一个负权边连接的两个顶点的任意一个顶点为起点向外松弛更新每次权值之和都会减小。 所以bellman-ford会返回一个bool值用来表明图中是否存在负权环。 6. 额外补充一点的是bellman-ford还有一个优化叫做SPFA用一个普通队列来统计每次松弛更新操作后存储权值改变了的结点如果这个结点改变了那就入队列下次循环时只需要对队列中存储的结点向外进行松弛更新操作即可那些没有被更改存储权值的结点就不需要入队列了因为这些顶点现存的值其实就已经是最短路径的权值了这样在每次循环时就不需要无脑遍历所有顶点作为起始点进行松弛更新了这样也可以进行优化。 但对于某些刁钻图的情况我从知乎上看到SPFA可能不会产生任何优化对于这些特殊情况这里也就不再讨论了因为本人的水平也就这么多了讨论不下去了。 5.多源最短路径
1. floyd-warshall算法是解决任意两点间的最短路径的算法也就是允许多个顶点作为源出发点故而称为多源最短路径。这个算法我觉得是图算法里面最不好理解的了因为他本质用的是动态规划而且还是二维的dp问题所以理解起来确实有点难搞。 我们需要求出从i到j的最短路径i和j代表任意的两个顶点的下标i到j的最短路径无非两种情况一种是i直接到j另一种是i先到其他顶点然后再到j中间可能经历过很多其他的结点所以针对这两种情况我们就可以列出dp的状态转移方程即当i到k加上k到j的权值小于i直接到j那么就更新shortPath这个二维dp数组存储的值k代表任意个中间结点的个数。 如果你看一下算法导论中关于动态规划的介绍其实就会发现动态规划和递归相比刚好是反过来的过程递归站在一个大问题的角度通过不断向深层次调用栈的过程将问题化解为最小的问题当最小的问题解决之后就开始回溯而动态规划是站在小问题的角度从下向上来解决问题一步一步解决小问题问题的规模逐渐变大最后将大问题解决floyd-warshall正是如此从下向上来解决问题所有的动态规划都是从下向上解决在向上解决的过程中如果要用到下面刚开始解决完毕的一些值时直接从dp数组里面去拿值即可光这么说确实很抽象但是想要理解floyd-warshall确实得需要你有一点dp的基础因为所有的dp问题都是先初始化dp数组然后逐步扩大问题的规模每次求解都会向前去找dp数组刚开始存储的值。 下面的代码也是这样的先将图中的边全部初始化到dp数组里面接下来就是列状态转移方程只要i到kk到j的权值和小于i到j那就更新dp数组存储的值同时我们要维护的二维prev数组也是如此
