程式員必須會的基本算法7-Kruskal算法(庫拉斯卡爾算法)

Kruskal算法

首先了解這個算法是用來幹嘛的

求最小生成樹的算法主要是普裡姆算法和克魯斯卡爾算法,是以它和prim算法一樣是用來用最小生成樹的

克魯斯卡爾(Kruskal)算法，是用來求權重連通圖的最小生成樹的算法。

基本思想：按照權值從小到大的順序選擇n-1條邊，并保證這n-1條邊不構成回路

問題背景

某城市新增7個站點(A,B,C,D,E,F,G)，現在需要修路把7個站點連通

各個站點的距離用邊線表示(權)，比如A–B距離12公裡

如何修路保證各個站點都能連通，并且總的修建公路總裡程最短?

解決

代碼解決

package basic;

import java.util.Arrays;

public class Kruskal
{
  //number表示邊的個數
  public static int number;
  public static char[] nodes;
  public static final int INF=Integer.MAX_VALUE;
  public static int[][] weight;
  
  public static void main(String[] args)
  {
    weight= new int[][]{
          /*A*//*B*//*C*//*D*//*E*//*F*//*G*/
      /*A*/ {   0,  12, INF, INF, INF,  16,  14},
      /*B*/ {  12,   0,  10, INF, INF,   7, INF},
      /*C*/ { INF,  10,   0,   3,   5,   6, INF},
      /*D*/ { INF, INF,   3,   0,   4, INF, INF},
      /*E*/ { INF, INF,   5,   4,   0,   2,   8},
      /*F*/ {  16,   7,   6, INF,   2,   0,   9},
      /*G*/ {  14, INF, INF, INF,   8,   9,   0}}; 
    nodes=new char[] {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
    kruskal(nodes, weight);
    
  }
  
  public static void InitNumber()
  {
    for(int x=0;x<nodes.length;x++)
    {
      for(int y=x+1;y<nodes.length;y++)
      {
        if(weight[x][y]!=INF)
        {
          number++;
        }
      }
    }
  }
  public static void kruskal(char[] nodes,int[][] weight)
  {
    //初始化number
    InitNumber();
    
    //傳回結果的索引index,和儲存結果的數組result
    int index=0;
    Edge[] result=new Edge[nodes.length-1];
    
    //用于儲存每一個節點在最小生成樹中的結尾是什麼
    int[] ends=new int[number];  
    
    //然後想的是擷取所有的邊,然後将所有的邊進行排序
    Edge[] edges = getEdges();
    Sort(edges);
    
    //然後是判斷每一條邊看看是否是需要加入到最小生成樹上面的
    for(int x=0;x<number;x++)
    {
      //然後現在想判斷的是這條邊的兩個節點的頂點是不是同一個頂點
      int end1 = GetEnd(ends, edges[x].start);
      int end2 = GetEnd(ends, edges[x].end);
      if(end1!=end2)
      {
        ends[end1]=end2;
        result[index++]=edges[x];
      }
    }
    System.out.println("最小生成樹為");
    for(int i = 0; i < index; i++) {
      System.out.println(result[i]);
    }
  }
  public static int GetEnd(int[] ends,char node)
  {
    int index=-1;
    for(int x=0;x<nodes.length;x++)
    {
      if(nodes[x]==node)
      {
        index=x;
        break;
      }
    }
    while(ends[index]!=0)
    {
      index=ends[index];
    }
    return index;
  }
  
  public static void Sort(Edge[] edges)
  {
    System.out.println("前:"+Arrays.toString(edges));
    for(int x=0;x<edges.length-1;x++)
    {
      for(int y=0;y<edges.length-1-x;y++)
      {
        if(edges[y].weight>edges[y+1].weight)
        {
          Edge temp=edges[y];
          edges[y]=edges[y+1];
          edges[y+1]=temp;
        }
      }
    }
    System.out.println("後:"+Arrays.toString(edges));
  }
  
  public static Edge[] getEdges()
  {
    int index=0;
    Edge[] edges=new Edge[number];
    for(int x=0;x<nodes.length;x++)
    {
      for(int y=x+1;y<nodes.length;y++)
      {
        if(weight[x][y]!=INF)
        {
          edges[index++]=new Edge(nodes[x], nodes[y], weight[x][y]);          
        }
      }
    }
    return edges;
  }
}
/*
 * 類Edge表示一條邊,儲存了start(邊的開頭字母),end(邊的結尾字母),weight(邊的權重)
 */
class Edge
{
  char start;
  char end;
  int weight;
  public Edge(char start, char end, int weight)
  {
    this.start = start;
    this.end = end;
    this.weight = weight;
  }
  @Override
  public String toString()
  {
    return "<" + start + "," + end + ">=" + weight;
  }
}