primmst.java

来自「个人学习图算法时写的源码 包括最小生成树, 最大网络流, DSF遍历, BSF」· Java 代码 · 共 40 行

package twf.weightedgraph.undirected;

import twf.weightedgraph.Edge;
import twf.weightedgraph.Graph;

public class PrimMST {
	private double[] wt;
	private Edge[] fr, mst;
	  public PrimMST(Graph G)
	    {
	      wt = new double[G.V()];
	      mst = new Edge[G.V()]; fr = new Edge[G.V()];
	      for (int v = 0; v < G.V(); v++) wt[v] = 2.0;
	      int min = -1;
	      for (int v = 0; min != 0; v = min)
	        { Edge e;
	          min = 0;
	          for (int w = 1; w < G.V(); w++)
	            if (mst[w] == null)
	              { double P = 0.0; e = G.edge(v, w);
	                if (e != null)
	                  if ((P = e.wt()) < wt[w])
	                    { wt[w] = P; fr[w] = e; }
	                if (wt[w] < wt[min]) min = w;
	              }
	          if (min != 0) mst[min] = fr[min];
	        }
	    }
	  
	  public void printMST() {
		  for (int i = 0; i < mst.length; i++) {
			  System.out.println(mst[i]);
		  }
	  }
	  
	  public Edge[] mst() {
		  return mst;
	  }
}