数据结构:克鲁斯卡尔算法(Kruskal)用于最小生成树
发布时间
阅读量:
阅读量
最小生成树算法:Prim算法与克鲁斯卡尔算法
克鲁斯卡尔算法
思路:优先队列结合并查集
Kruskal算法
【算法简介
代码设计
1、通过引入优先级队列机制,将权重较低的边置于队列前端,确保每次选取的边均为当前权重最小的选项。
2、借助并查集的数据结构特性,利用查找与合并操作将属于同一连通区域的顶点统一归于相同的父节点之下。如此一来,在判断是否形成环路时,仅需验证两个顶点的父节点是否一致即可完成判定。
1.1 存图方式
采用结构体数组的方式对图进行存储;
//因为每条边需要保存数据 起始节点 ,到达节点 ,花费(路的长度)
struct edge{
int start;//出发节点
int target;//目标节点
int cost;//花费(路径的长度)
};
//因为定义了边类型,需要使用优先队列,即需要比大小,需要重新定义<
bool operator<( edge a, edge b ){//升序
if(a.cost>b.cost)
return true;
else
return false;
}
全部评论 (0)
还没有任何评论哟~
