Dijkstra算法--这是我职业生涯中唯一一个会写，却叫不上名字的算法Dijkstra算法是一种单源最短路径算法，用于找出图中从一个源点到其他所有点的最短路径。该算法的原理是采用贪心策略，每次将距离源点最近的点加入到已确定最短路径的集合中，并更新其它节点的距离。具体实现过程如下：初始化距离数组dist[]，源点距离为0，其余点距离为无穷大。将所有点加入到未确定最短路径的集合中。在未确定最短路径的集合中找出距离源点最近的节点v，并将其加入到已确定最短路径的集合中。对节点v的所有邻居节点u进行更新，如果dist[u]>dist[v]+w(v,u)，则更新dist[u]=dist[v]+w(v,u
1.连通块的定义块内每个点之间都有一条路径。2.思路我们可以用dfs深度优先搜索：从一个点出发遍历图将遍历过的点全部标记，标记过的点则不会再遍历到。再写一个循环枚举所有的点（枚举起点），如果没标记就代表可以作为起点，数量加一，进行dfs标记点。3.代码 #includeusingnamespacestd;longlongn,m,ans;//n点数，m边数，ans连通块数量。boola[105][105],vis[105];//a邻接矩阵，vis标记。voiddfs(intx){ for(inti=1;i>n>>m; for(inti=1;i>u>>v; a[u][v]=1; a[v][u]
目录1.DFS和BFS1.1.DFS深度优先搜索1.2.BFS广度优先搜索2.树与图的遍历：拓扑排序3.最短路 3.1.迪杰斯特拉算法3.2.贝尔曼算法3.3.SPFA算法3.4.多源汇最短路Floy算法4.最小生成树4.1.普利姆算法4.2.克鲁斯卡尔算法5.二分图：染色法，匈牙利算法5.1.染色法5.2.匈牙利算法1.DFS和BFS1.1.DFS深度优先搜索深度优先搜索（Depth-FirstSearch,DFS）是一种用于遍历或搜索树或图的算法。它从起点开始，沿着一个路径一直到达最深的节点，然后回溯到之前的节点，继续探索下一个路径，直到所有的节点都被访问过。DFS使用一个栈来存储待访问的
图的基本概念无向图边是没有方向的，也就是双向的结点V={v1,v2,...,v7}\mathcal{V}=\{v_1,v_2,...,v_7\}V={v1,v2,...,v7}边ε={e1,2,e1,3,...,e6,7}\varepsilon=\{e_{1,2},e_{1,3},...,e_{6,7}\}ε={e1,2,e1,3,...,e6,7}图G={V,ε}\mathcal{G}=\{\mathcal{V},\varepsilon\}G={V,ε}有向图边是有方向的，也就是单向的无权图边没有权重，也可以理解为权重都是1有权图边有权重图的数据结构邻接矩阵与邻接表无向无权图邻接
文章目录优缺点伪代码具体流程效率问题代码优缺点优缺点先明说，优点RRTStar适用于任何地图，不像AStar，Dijkstra那样受限于栅格地图。缺点：1.找到的路径可能不是最优的；2.路径可能不符合机器人的运动学动力学模型；3.效率问题。伪代码具体流程给出起点和终点，以及设置好障碍物的地图，如下所示，将起点记作是根节点。进行空间撒点采样，在空间中随机选择一点Xrand。（这里对应伪代码当中的Sample()函数）接着寻找距离Xrand最近的一个已知节点Xnear（这一步对应伪代码当中的near()函数）。因为当前只有一个根节点（起点），所以根节点即为Xnear。“树的生长”（执行Steer函
文章目录多源汇最短路：1125.牛的旅行传递闭包：343.排序最小环：344.观光之旅345.牛站flody的四个应用：多源汇最短路传递闭包找最小环恰好经过k条边的最短路倍增多源汇最短路：1125.牛的旅行1125.牛的旅行-AcWing题库直径概念：同一连通块中，两个距离最远的点之间的距离如何求直径？由于图中存在着两个连通块，所以直接对全图做一个flody，就能更新出任意两点间的距离，距离大于正无穷的一半时，说明两点处于不同连通块中题目要连接两个连通块，并计算所有连接方法下，原连通块与新连通块中，最大直径的最小值可以枚举所有的连接方式，维护出新连通块的直径最小值，将其与原连通块的两个直径比较
文章目录lcaTarjan板子题：1172.祖孙询问lca或tarjan：1171.距离356.次小生成树352.闇の連鎖lcaO(mlogn)O(mlogn)O(mlogn)，n为节点数量，m为询问次数，lca是一种在线处理询问的算法自己也是自己的祖先倍增：fa(i,j)fa(i,j)fa(i,j)表示从i开始，向上走2j2^j2j步走到的点j=0，走到父节点j>0，分两步走，先走到2j−12^{j-1}2j−1步再走2j−12^{j-1}2j−1步，那么一共就会走2j2^j2j步，fa(i,j)=fa(fa(i,j−1),j−1)fa(i,j)=fa(fa(i,j-1),j-1)fa(i,
文章目录裸题：904.虫洞01分数规划：361.观光奶牛特殊建图与01分数规划+trick：1165.单词环裸题：904.虫洞904.虫洞-AcWing题库//虫洞是负权且单向边，道路是正权且双向边，题目较裸，判断有无负环即可#include#includeusingnamespacestd;constintN=510,M=6010;inth[N],e[M],ne[M],w[M],idx;intn,m,k;intdis[N],cnt[N];intq[N];boolst[N];voidadd(intx,inty,intd){e[idx]=y,ne[idx]=h[x],w[idx]=d,h[x]=
算法笔记-lc-827.最大人工岛题目简介示例提示解法标记+合并并查集+枚举题目简介给你一个大小为nxn二进制矩阵grid。最多只能将一格0变成1。返回执行此操作后，grid中最大的岛屿面积是多少？岛屿由一组上、下、左、右四个方向相连的1形成。示例示例1:输入:grid=[[1,0],[0,1]]输出:3解释:将一格0变成1，最终连通两个小岛得到面积为3的岛屿。示例2:输入:grid=[[1,1],[1,0]]输出:4解释:将一格0变成1，岛屿的面积扩大为4。示例3:输入:grid=[[1,1],[1,1]]输出:4解释:没有0可以让我们变成1，面积依然为4。提示n==grid.lengthn
算法笔记-lc-827.最大人工岛题目简介示例提示解法标记+合并并查集+枚举题目简介给你一个大小为nxn二进制矩阵grid。最多只能将一格0变成1。返回执行此操作后，grid中最大的岛屿面积是多少？岛屿由一组上、下、左、右四个方向相连的1形成。示例示例1:输入:grid=[[1,0],[0,1]]输出:3解释:将一格0变成1，最终连通两个小岛得到面积为3的岛屿。示例2:输入:grid=[[1,1],[1,0]]输出:4解释:将一格0变成1，岛屿的面积扩大为4。示例3:输入:grid=[[1,1],[1,1]]输出:4解释:没有0可以让我们变成1，面积依然为4。提示n==grid.lengthn
