最小生成树
2022-05-16 11:30:22 18 举报AI智能生成
算法
作者其他创作
大纲/内容
prim算法
每次选择距离已加入的集合最近的点尝试加入，循环n个点停止
visit[i]数组表示节点是否访问过，两个点均访问过视为有环路，两层循环遍历一个找过一个没找过的
visit[i]数组表示节点是否访问过，两个点均访问过视为有环路，两层循环遍历一个找过一个没找过的
时间复杂度：o（V²）点
克鲁斯卡尔算法
将边按权值排序，每次选最小边，并查集检测无环路，选够n-1个边停止
时间复杂度：o（ElogE）
最短路径算法
迪杰斯特拉算法
单源最短路径，选择起始点，两集合S和U保存已计算和未计算的点，dist[i]保存当前最近距离
每次从dist[i]中选最近的节点，更新距离
时间复杂度：o（n²）
克鲁斯卡尔算法
多源点最短路径，两个矩阵分别保存两个点的距离和前驱节点
顺序选择每个节点作为中间节点，依次更新每个节点之间的距离和前驱节点
时间复杂度：o（n^3）
收藏
收藏
0 条评论
下一页
