目录

243 图 Floyd Warshall 算法实现2

244 图 Floyd Warshall 算法实现3

245 图 Floyd Warshall 算法实现4

246 图 最小生成树 Prim

247 图 最小生成树 Kruskal

248 图 并查集 1

249 图 并查集 2

250 图 并查集 路径压缩

251 图 并查集 UnionBySize

252 贪心算法 介绍

253 零钱兑换II 递归 实现

---

243 图 Floyd Warshall 算法实现2

244 图 Floyd Warshall 算法实现3

增加prev值。

 举个例子去理解这个输出结果。

比如第一行，v1到v1自己是null，v1到v2是null，因为不连通，v1到v3是连通的，而且v3的prev值是v1，v1到v4是null，因为不连通。

 第一行的第二个的意思是，v1到v2 是从v1到v3到v4最后到v2，因此v2的prev就是v4

245 图 Floyd Warshall 算法实现4

什么时候发现有负环呢？

就是对角线上出现了负数。

246 图 最小生成树 Prim

247 图 最小生成树 Kruskal

 

248 图 并查集 1

以谁为基准，谁就是老大，也就是说，索引和值相等的就是老大。

union不代表连接实现  

249 图 并查集 2

依次实践证明这个方法。 

250 图 并查集 路径压缩

251 图 并查集 UnionBySize

x 是老大

 

 这样子，就不用考虑x和y谁是老大小弟了，直接传进去就可以了，它会自己判断谁是老大谁是小弟。

也可以改为下面这个，结果是一样的。

252 贪心算法 介绍

253 零钱兑换II 递归 实现