Jerry404Lee

图论

algorithm(1) AVL(1) BFS+队列(2) BST(2) git(1) GO(4) IDEA(1) java(15) java核心API(3) java设计模式(5) linux(1) OS真象还原(1) PAT(11) PAT做题技巧(1) redis(4) Spring(1) STL(3) 三个一工程(9) 二叉树(3) 二维指针(1) 动态规划-dp(3) 堆(1) 复试(3) 多线程(1) 大数问题(5) 实验楼(1) 快速排序(1) 技巧题(5) 操作系统(1) 数论(4) 普通树(1) 机试(1) 栈(1) 模板(4) 活用递推(1) 牛客算法(7) 类型转换(1) 行数据的处理(1) 计算机网络(3) 读书笔记(1) 递归入门(3) 高频算法题(1)

/ 注册

全部文章 / 图论（共13篇）

最小生成树的胡思乱想--做减法

最小生成树的胡思乱想–做减法今天看到最小生成树的算法忽然想到为什么现在的做法都是在做加法呢？为什么不尝试一下减法呢？比如说我们的顶点数n，边数m n和m相差不多。如果我们做加法的话要做 n-1条，假如说n比较大但是我们如果**做减法，应该只需要（ m-（n-1））...

2021-04-29

0 522

最小生成树--prim算法

最小生成树–prim算法首先说明，Dijkstra算法和prim算法实际上是相同的思路，只不过是数组d[]的含义不同。详见算法笔记 P404 prim算法的基本思想是对图G设置集合S（就是个巨型防护罩），用来存放已经被访问的顶点（就是被攻占的城市），然后执行n次下面的两个步骤： 1.每...

2021-04-29

0 477

最小生成树--kruskal

最小生成树–kruskal 也加克鲁斯卡尔算法。 kruskal算法的思想简单说来就是：每次选择图中最小边权的边，如果边两端的顶点在不同的连通块中，就把这条边加入最小生成树中。如果是稠密图（边多），用prim算法；如果是稀疏图（边少），用kruskal算法，或者用我自己想的“做减法”。 ...

2021-04-29

0 608