最小生成树prim.txt

PRIM求最小生成树

/*
* Main.java
* 
* Created on 2007-12-2, 7:53:33
* 
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
package eprim;
import java.util.*;
/**
*
* @author Administrator
*/
class AdjMWGraph
{
    Vector<String> edge=new Vector<String>();
    Vector<String> result=new Vector<String>();
    Vector<Integer> weight=new Vector<Integer>();
    int mincost;
    //初始化
    AdjMWGraph()
    {
        edge.add("B A 50");
        edge.add("C A 60");
        edge.add("C G 45");
        edge.add("B D 65");
        edge.add("C D 52");
        edge.add("D G 42");
        edge.add("B E 40");
        edge.add("E D 50");
        edge.add("E F 70");
        edge.add("D F 30");
    }
    //判断字符串中是否存在子串
    boolean sub(String subs,String s)
    {
       boolean b=false;
       String [] newstring=s.split(" ");
       if(newstring[0].compareTo(subs)==0)b =true;
       else if(newstring[1].compareTo(subs)==0)b=true;
       return b;
    }
    void prim()
    {
       result.add("A");
       int n=0,m=0;
       for(int k=0;k<6;k++)
       {
           mincost=9999;
       for(int j=0;j<result.size();j++)
       {                 
           for(int i=0;i<edge.size();i++)
       {
           if(sub(result.get(j),edge.get(i))==true)
           {   
               String [] newString =edge.get(i).split(" ");
               if(mincost>Integer.parseInt(newString[2]))
               {
                   n=i;m=j;
                   mincost=Integer.parseInt(newString[2]);
               }
           }
       }        
       }  
        String[] s1=edge.get(n).split(" ");
        if((result.get(m).compareTo(s1[0]))!=0) 
        result.add(s1[0]);
        else if((result.get(m).compareTo(s1[1]))!=0) result.add(s1[1]);
        edge.remove(n);
        weight.add(mincost); 
       }
    }
    void display()
    {
        for(int i=0;i<result.size()-1;i++)
        {
            System.out.println(result.get(i)+" "+result.get(i+1)+" "+weight.get(i));
        }
    }
}
public class Main {
    /**
     * @param args the command line arguments
     */
    AdjMWGraph node;
    int num;
    Main()
    {
        node=new AdjMWGraph();
        num=node.edge.size();
        node.prim();
        node.display();
    }
    public static void main(String[] args) {
        Main oooo=new Main();
    }
}