lisl1233

分类

字符串(6) 最小生成树(2) 最短路径(5)

/ 注册

全部文章（共13篇）

最短路径--floyed

最短路径----floyed 多元最短路径思路: 遍历全数组，看每个点是否可以松弛，如果可以，将松弛完与未松弛进行比较，取值最小的方式。时间复杂度O(n³) Code: #include<iostream> #include<cmath> #inclu...

2021-07-13

1 467

最小生成树--Kruskal

最小生成树----Kruskal Kruskal与Prim不同的是Prim是以任意一个点为起点，一次向其他点遍历，而Kruskal则是以边为起点，向其他边遍历,Kruskal的时间复杂度远远小于Prim。思路：先将所有的边排序依次找出边权最小的边，并查集判断他是否以连接如果未连接，则将其连...

2021-07-13

1 477

最小生成树--Prim

最小生成树----Prim 思路：任意找一个点遍历这个点的所有边，并找到未经过点的且权值最小的边，将其累加起来通过这条边，找到下一个点重复2和3，直到遍历所有的点时间复杂度O(n²)Code： #include<iostream> #include&l...

2021-07-13

1 467