[编程笔记]-Bipartite_Graph_Maximum_Match(Hungary_Algorithm)二分图最大匹配（匈牙利算法）

[编程笔记]-Bipartite_Graph_Maximum_Match(Hungary_Algorithm)二分图最大匹配（匈牙利算法）

二分图最大匹配就是求出在二分图中，最多有多少对点能完成匹配。 有时还会让你输出方案。 更高级的其实是带权的匹配问题，但鉴于这篇博客本意不在于此，所以就只讲解匈牙利算法了。 当然还有更高级的我忘了，到时候再说吧。 匈牙利算法其实很简单，以左侧点为基准，对于每个点，尝试每个与它相连的右侧点： 如果右侧点没有匹配，那就直接上；如果右侧点有匹配了，就让跟它匹配的左侧点尝试找别的可以匹配的点（也就是递归），
编程笔记 > 图论树论
#原创 #编程 #c++ #笔记 #图论 #二分图 #匈牙利算法
[编程笔记]-Bipartite_Gragh_Determination(Staining_Method)二分图判定（染色法）

[编程笔记]-Bipartite_Gragh_Determination(Staining_Method)二分图判定（染色法）

作用判定一个图是不是二分图（可以分成左右两边、边只存在于两边之间而不在某一边内部的图） 二分图正规定义：图中不含奇数环。 实现就是用DFS或BFS或其他遍历方式遍历整个图，尝试给每两个相邻点染上不同颜色，最多两色，如果成功就是二分图。 #代码染色特别好理解，所以重点实在遍历上面。[编程笔记]-DFS深度优先搜索[编程笔记]-BFS广度优先搜索（就不放代码了(～￣▽￣)～） 完结撒花o(￣︶￣)o
编程笔记 > 图论树论
#原创 #编程 #c++ #笔记 #图论 #二分图 #染色法
[编程笔记]-Kruskal

[编程笔记]-Kruskal

作用多在稀疏图中生成最小生成树 实现 将每条边从小到大排好序。 找到一条连接两个不同集合的边权最小的边，将其加入确定的边中。 重复n-1次，即所有点都加入了最小生成树。 特殊地，判断连接的是否是两个不同集合，推荐使用并查集。[编程笔记]-Union_Find_Set并查集 代码123456789101112131415161718192021222324252627282930313233343
编程笔记 > 图论树论
#原创 #编程 #c++ #笔记 #图论 #树论 #最小生成树 #Kruskal
[编程笔记]-Prim

[编程笔记]-Prim

实现和Dijkstra基本一模一样。 不过它每次找的是距离当前生成的树最近的节点，不是距离树根最近的节点。 [编程笔记]-Dijkstra(Plain)迪杰斯特拉（朴素版） 初始化：设立一个集合S（空）储存所有已在生成树中的点，并设立距离dis数组，除了起点设为0外，其他点都设为正无穷。 在所有点中，找一个不在S里并且dis最小的点t 把t加入集合S，并且更新所有与之相连的点的距离。 重复执行2
编程笔记 > 图论树论
#原创 #编程 #c++ #笔记 #图论 #树论 #最小生成树 #Prim
[编程笔记]-Minimum_Spanning_Tree_Problem(General)最小生成树问题总概

[编程笔记]-Minimum_Spanning_Tree_Problem(General)最小生成树问题总概

Prim特别像Dijkstra，除了作用不一样，别的几乎都一样，甚至优化方式都一样Σ(っ °Д °;)っ 朴素版时间复杂度O(n2) 通常用来解决稠密图。 堆优化版说实话，不常用，因为Kruskal比它好写。 时间复杂度O(mlogn)。 常用来解决稀疏图。 因为它不常用，也因为它的优化方法和Dij一样，所以就不专门讲了 Kruskal时间复杂度O(mlogm)（和O(mlogn)同一个量级）。
编程笔记 > 图论树论
#原创 #编程 #c++ #笔记 #图论 #树论 #最小生成树
[编程笔记]-Floyd

[编程笔记]-Floyd

前言你以为这篇最短路和其他最短路差了一天的时间吗？不，实际上只差了一个小时(ノへ￣、) 现在是00: 24 半夜三更发癫很正常，如有发癫您就别管那点鸡毛小事了hhh 作用用于多源汇最短路问题，也就是有多个源点的最短路问题。 实现 邻接矩阵存储所有的边 直接上三重循环。啊就是找起点终点和跳板点然后通过跳板点更新dis嘛不想解释了看代码吧。1234567for(int k=1;k<=n;k++)
编程笔记 > 图论树论
#原创 #编程 #c++ #笔记 #图论 #最短路 #Floyd
[编程笔记]-SPFA

[编程笔记]-SPFA

实质关于SPFA，它亖了 就是对Bellman-Ford算法的一种优化。事实证明优化地很成功，直接给BF差不多干没了 可以得出，节点i路程变化，当且仅当指向i的节点的路程变化，然后就能写出一个接近bfs的算法。 特性通常情况下，SPFA是快于Dijkstra的。 ！！！但是！SPFA它亖了容易被卡啊！被卡了就真亖了！！！ 实现 把起点插入队列 取出队头，更新队头的所有出边。 每个更新成功的出边，都
编程笔记 > 图论树论
#原创 #编程 #c++ #笔记 #图论 #最短路 #SPFA
[编程笔记]-Bellman-Ford

[编程笔记]-Bellman-Ford

用处常用于在有负权边的有向无环图中进行最短路判断。 要是有负权回路就没有结果了（或结果是负无穷）。解释：每转一圈距离就减一点，那我转啊转啊转啊转啊……然后就不出来了(～￣▽￣)～ 事实上用死了的SPFA更好o(￣︶￣)o 因此，事实上，一般用BELLMAN-FORD的都是有边数长度限制的题目，具体会在世纪意义中说明。 实现操作重复执行n次：遍历所有边，尝试更新每个边指向点的dis。（松弛操作） 啊
编程笔记 > 图论树论
#原创 #编程 #c++ #笔记 #图论 #最短路 #Bellman-Ford
[编程笔记]-Dijkstra(HeapOptimized)迪杰斯特拉（堆优化）

[编程笔记]-Dijkstra(HeapOptimized)迪杰斯特拉（堆优化）

概念其实就是用堆来优化Dijkstra算法（废话）。由于O(logm)（STL）与O(logn)（手写）为同一数量级，所以还是推荐直接用STL里的优先队列了。 其实就是优化了找当前距离最短的点的过程嘛。 由于是稀疏图，所以要用链式前向星做了。 代码事实上这种优化算法往往比朴素版更常见~ 12345678910111213141516171819202122232425262728293031323
编程笔记 > 图论树论
#原创 #编程 #c++ #笔记 #图论 #最短路 #Dijkstra #堆
[编程笔记]-Dijkstra(Plain)迪杰斯特拉（朴素版）

[编程笔记]-Dijkstra(Plain)迪杰斯特拉（朴素版）

前言与之前不同的是，图论的问题，重实现，而不重原理，所以这几篇博客会重点记录实现部分。 实现 初始化：设立一个集合S（空）储存所有已确定最短距离的点，并设立距离dis数组，除了起点设为0外，其他点都设为正无穷。 在所有点中，找一个不在S里并且dis最小的点t 把t加入集合S，并且更新所有与之相连的点的距离。 重复执行2、3步直到每个点都加入集合S 代码update 2024/8
编程笔记 > 图论树论
#原创 #编程 #c++ #笔记 #图论 #最短路 #Dijkstra