0
我想在Java中实现Prim算法。我面临的问题是同一个顶点不止一次被添加，因此我的MST的重量会出错。Prim的算法实现不止一次添加顶点
我已经使用了以下的数据结构：
标记：长度的数组= | V |，标记为[I] = 48意味着尚未MST，和49是指顶点i是MST。
堆：一个长度= | 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;
}
}