Prim 的算法实现多次添加顶点

Question

我正在尝试在 Java 中实现 Prim 算法。我面临的问题是同一个顶点被添加了不止一次，因此我的 MST 的权重是错误的。

我使用了以下数据结构：

marked: 一个长度为|V|的数组，marked[i]=48表示尚未在MST中，49表示顶点i在MST中。

heap：长度为|V|的二维数组，其中第一行给出顶点，第二行给出相应的wts。

adj_list: 图的邻接表表示。

wt_list：adj_list.

表示的边对应的wts

pos:长度为|V|的数组其中 pos[i] 给出顶点 i 在堆中的位置。

这是我的 java 源代码：

import java.util.*;
class PRIM
{
 private ArrayList<LinkedList<Integer>> adj_list;
 private ArrayList<LinkedList<Integer>> wt_list;
 private static Scanner s;
 private char []marked;
 int []pos;
 private int [][]heap;
 private int size;
 public void create_graph(int v)
 {     
     size=v;
     marked=new char[v];
     pos=new int[v];
     for(int i=0;i<v;++i)
     {marked[i]=48;}
     adj_list=new ArrayList<LinkedList<Integer>>();
     wt_list=new ArrayList<LinkedList<Integer>>();
     s=new Scanner(System.in);
     for(int i=0;i<v;++i)
     {
      System.out.println("how many vertices adjacent to vertex "+(i)+" and what are they and their wts");
      int k=s.nextInt();
      adj_list.add(new LinkedList<Integer>());
      wt_list.add(new LinkedList<Integer>());
      for(int j=1;j<=k;++j)
      {
          adj_list.get(i).add(s.nextInt());
          wt_list.get(i).add(s.nextInt());
      }
     }

 }
 public static void main(String []args)
 {
     s=new Scanner(System.in);
     System.out.println("enter the number of vertices");
     int n=s.nextInt();
     PRIM g=new PRIM();

     g.create_graph(n);
     g.initialize_heap(n);
     g.build_heap();    
     /*ASSUMING THE ARBITRARY VERTEX TO BE 0*/   
     System.out.println("The cost of MST is "+g.MST());
 }
 public void initialize_heap(int v)
 {
     heap = new int [2][v];
     for(int i=1;i<v;++i)
     {
         heap[0][i]=i;
         heap[1][i]=100;
         pos[i]=i;
     }
     pos[0]=0;
     heap[0][0]=0;
     heap[1][0]=0;          
 }
 public void build_heap()
 {  
     for(int i=size/2;i>=1;--i)
      heapify(i);  
 }
 public int MST()
 {
     int cost=0;
     while(size!=0)
     {
         cost+=extract_min();
         set_key();         
     } 
     return cost;
 }
 public void set_key()
 {
     for(int i=0;i<adj_list.size();++i)
     {
         if(marked[i]==48)
         {
             int min=100;
             for(int j=0;j<adj_list.get(i).size();++j)
             {
                 int v=adj_list.get(i).get(j);
                 if(marked[v]==49)
                 {
                     if(wt_list.get(i).get(j)<min)
                      min=wt_list.get(i).get(j);
                 }
             }
             if(min<heap[1][pos[i]]&&marked[i]==48)
             decrease_key(pos[i],min);
         }

     }
 }
 public void decrease_key(int i,int m)
 {
     heap[1][i]=m;int parent;
     while(i>0)
     {
         parent=i/2;
         if(heap[1][parent]>heap[1][i])
          exchange(i,parent);
         else break;
         i=i/2;
     }
 }
 public int extract_min()
 {
     int min=heap[1][0];
     marked[heap[0][0]]=49;
     System.out.println("Vertex "+heap[0][0]+" is added");     
     exchange(0,size-1);
     --size;
     heapify(1);
     return min;     
 }
 public void heapify(int i)
 {
     int l=2*i,r=l+1;
     int smallest;
     if(l<=size&&heap[1][l-1]<heap[1][i-1])
      smallest=l;
     else smallest=i;
     if(r<=size&&heap[1][r-1]<heap[1][smallest-1])
      smallest=r;
     if(smallest!=i)
     {
         exchange(i,smallest);
         heapify(smallest);
     }
 }
 public void exchange(int i,int j)
 {
     pos[heap[0][i]]=j;
     pos[heap[0][j]]=i;
     int temp=heap[0][i];
     heap[0][i]=heap[0][j];
     heap[0][j]=temp;

     temp=heap[1][i];
     heap[1][i]=heap[1][j];
     heap[1][j]=temp;
 }
}

Answer 1

天哪，这么小的bug，我还以为我没看懂PRIM的算法呢

我的 exchange 方法适用于真实索引，但您会注意到我的 heapify 方法基于从 1 开始的假索引, 所以基本上我需要打电话

exchange(i-1,smallest-1);

而不是

exchange(i,smallest);

现在我的代码运行得非常完美。

Prim 的算法实现多次添加顶点

Prim's Algorithm implementation adding vertices more than once

java

algorithm

minimum-spanning-tree