目录题目：村村通并查集 题目：最小生成树kruskal算法prim算法 先引入问题：要在n个城市之间铺设光缆，主要目标是要使这n个城市的任意两个之间都可以通信，但铺设光缆的费用很高，且各个城市之间铺设光缆的费用不同，因此另一个目标是要使铺设光缆的总费用最低。这就需要找到带权的最小生成树。说白了就是将此图连通起来的最小代价。 对于一个有N个点的图，边一定是大于等于N-1条的。图的最小生成树，就是在这些边中选择N-1条出来，连接所有的N个点。这N-1条边的边权之和是所有方案中最小的有两种算法：prim和kruskal前者适合稠密图，后者适合稀疏图(不然炸你内存)
一.Java查找算法之折半查找 相关知识:折半查找又叫作二分查找，是一种在有序数组中查找某一特定元素的搜索算法，使用二分可以极大地缩小我们搜索的时间复杂度第1关：折半查找（二分查找）1.任务描述本关任务：给定一个排好序的数组，然后输入另一个整数，判断该整数在数组中的什么位置，返回该整数第一次出现的位置（位置从0开始），否则返回-1。样例1:测试输入:n=6，nums=[-1,0,3,5,9,12]，T=9预期输出:4解释:9出现在nums中并且下标为4样例2:测试输入:n=6，nums=[-1,0,3,5,9,12],T=2预期输出:-1解释:2不存在nums中因此返回-12.思
目录预备知识模板1：无向图的桥模板2：无向图的割点模板3：有向图的强连通分量 讲之前先补充一下必要概念：预备知识无向图的【连通分量】：即极大联通子图，再加入一个节点就不再连通（对于非连通图一定两个以上的连通分量）无向图的【(割边或)桥】：即去掉该边，图就变成了两个连通子图无向图的【割点】：将该点和相关联的边去掉，图将变成两个及以上的子图注意：有割点不一定有桥，但是有桥一定有割点 无向图的【边双连通图】:无向图中不存在桥，即删除一条边后仍然连通(每两个点间有至少两条路径，且路径上的边互不重复) 无向图的【点双连通图】:无向图中不存在
目录今天知识点并查集统计集合元素个数和每个元素的信息并查集处理关系层次从而判断节点关系POJ1988 思路：POJ1182 思路： POJ1988有n个栈每个栈中有一个方块，现要执行n次操作。一种是移数，一种是计数移数M：把包含x的栈整体移动到y栈顶计数C：统计X方块下面的方块数输入：6M16C1M24M26C3C4 思路：我们不需要模拟，我们只需要等价即可，每次操作无非是把一个链表接到了另一个链表上，这完全可以用并查集实现。 设置fa数组表示集合号，cnt表示x号栈中的数量，d为x下方的数量
684.冗余连接题目：树可以看成是一个连通且无环的无向图。给定往一棵n个节点(节点值1～n)的树中添加一条边后的图。添加的边的两个顶点包含在1到n中间，且这条附加的边不属于树中已存在的边。图的信息记录于长度为n的二维数组edges，edges[i]=[ai,bi]表示图中在ai和bi之间存在一条边。请找出一条可以删去的边，删除后可使得剩余部分是一个有着n个节点的树。如果有多个答案，则返回数组edges中最后出现的那个。题目链接：684.冗余连接代码如下：修改join函数classSolution{publicint[]father;publicint[]findRedundantConnect
文章目录1.代码仓库2.图的基本表示的比较3.邻接矩阵：Array和TreeSet3.1图示3.2Array主要代码解析3.3测试输出3.4使用TreeSet的代码4.邻接表：LinkedList4.1图示4.2LinkedList主要代码解析4.3测试输出5.完整代码5.1邻接表-Array5.2邻接表-TreeSet5.3邻接矩阵-LinkedList5.4输入文件1.代码仓库https://github.com/Chufeng-Jiang/Graph-Theory/tree/main/src/Chapt01_Adjacency2.图的基本表示的比较3.邻接矩阵：Array和TreeSet
目录概述考点：邻接矩阵，矩阵的计算及含义，完全图，补图，平面图的相关概念，欧拉图，最小生成树，最优二叉树一.图编辑 二.路和回路2.12.2连通与可达1.可达2.连通三.图的矩阵表示3.1邻接矩阵3.2可达性矩阵3.3无向图的完全关联矩阵3.4有向图的完全关联矩阵四.特殊的图4.1欧拉图和哈密尔顿图五.平面图六.对偶图七.树与生成树7.1生成树：7.2有序树与二叉树之间的转换 7.3最优树与哈夫曼算法 7.4编码问题概述考点：邻接矩阵，矩阵的计算及含义，完全图，补图，平面图的相关概念，欧拉图，最小生成树，最优二叉树一.图 二.路和回路2.1②若路中的所有边互不相同，则称为迹； 若回路中
图基础#mermaid-svg-LMb171qOymmKEHRx{font-family:"trebuchetms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-LMb171qOymmKEHRx.error-icon{fill:#552222;}#mermaid-svg-LMb171qOymmKEHRx.error-text{fill:#552222;stroke:#552222;}#mermaid-svg-LMb171qOymmKEHRx.edge-thickness-normal{stroke-width:
文章目录一、中国邮递员问题1.与欧拉回路的关系2.Edmonds-Johnson算法3.一个例子二、平面图上的最大割问题1.割2.最大割及其NP\bold{NP}NP完全性3.平面图上的最大割问题4.奇回路覆盖5.转化为一般图最大匹配6.一个例子三、顶点图上最大割问题的NP\bold{NP}NP完全性参考资料一、中国邮递员问题中国邮递员问题（ChinesePostmanProblem,CPP）是图论中的一个著名问题，它是在1960年由我国学者管梅谷首先提出并研究的。简单来说，就是问：一个邮递员从邮局出发，把一个城市的所有街道都至少走一遍，最后回到邮局，问怎样使他走的总路程最小？这个问题有许多现
在最小生成树算法中比较经典的算法有两个（1）Kruskal'sAlgorithm(克鲁斯卡尔算法) (2)Prim'sAlgrorithm（普利姆算法）（代码在文章最后）图的最小生成数就是在图中提取出一个树状结构，包含图中所有的顶点，任意两个顶点之间都是可达的，但是不能有环存在，其中该树结构中所有边的权重和在所有其他的由图生成的树中最小下面首先对两个算法进行介绍：一、Kruskal'sAlgorithm(克鲁斯卡尔算法) 伪代码：1.首先将图中所有边按照权重从小到大进行排序 2. 按照排好的顺
