构建最小生成树普利姆算法和克鲁斯卡尔算法(P&C)

2021/12/30 11:07:39

本文主要是介绍构建最小生成树普利姆算法和克鲁斯卡尔算法(P&C),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

  普利姆算法和克鲁斯卡尔算法的思想可以归为贪心算法即:以每次局部最优解最后得全局最优解。

  相同点:

    1. 都适用于无向图。
    2. 都是用了贪心思想    

  不同点:

    1. 普利姆算法是顶点优先,克鲁斯卡尔是边优先。二者应对不同情况效率不同。
    2. 普利姆算法平均时间复杂度为O(n^2),是顶点数的平方。
    3. 克鲁斯卡尔算法平均时间复杂度取决于选用的排序算法,是和边数相关的。

  普利姆算法分析如下:

   

for (int k = 0; k < g.n; k++) {
// 用邻接矩阵存储无向图, 维护一个 lowcost[],一个vset[] vset数组用于记录已经选择的顶点  
for (int i = 0; i < g.n; i++){
  //找到lowcost中 没有被选择过的最小值
  if (vset[i] == 0 && lowcast[i] < min){
    min = lowcast[i];
    min_index = i;
  }
}
// 将 min_index 点并入
vset[min_index] = 1;
//维护lowcost数组
for (int j = 0; j < g.n; j++){
  // min_index 点位新加入的点, 只要该点到其他点的距离小于 lowcost[j] 就覆盖,由此lowcost[]一直都是子树到各点的最小距离
  if (vset[j] == 0 && g.edges[min_index][j] < lowcost[j] ){
    lowcost[j] =g.edges[min_index][j];
  }
  }
}


  克鲁斯卡尔算法运用并查集工具判断是否形成回路。 并查集本质是在一个数组存了一棵二叉树,通过查找不同子节点的根节点判断是否会形成回路。

//并查集工具
public int getRoot(int a){
  // v[] 存放二叉树
  while(a != v[a]){
    a = v[a];
  }
  return a;
}
//定义边的类 包含边的左节点有节点和边的长度
class Edge{
  int leftNode;
  int rightNode;
  int length
}
//初始化并查集工具用到的数组
for (int i = 0; i < g.n; i++){
  v[i] = i;
}
// 将边按照从小到大顺序排列
sort(Edge[] edges, g.E);
for (int i = 0; i < g.e; i++){
  // 获取左右两个节点的根节点
  leftNode = getRoot(edges[i].leftNode);
  rightNode = getRoot(edges[i].rightNode);
  if (leftNode != rightNode){
    // 说明是两棵独立的子树 可以合并
    v[leftNode] = rightNode;
  }
}

  

 



这篇关于构建最小生成树普利姆算法和克鲁斯卡尔算法(P&C)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程