(Java) K法與P法 求最小擴張樹

1. 
   
2. class Kruskal {  
3.     public static int VERTS=6;  
4.     public static int v[]=new int[VERTS+1];  
5.     static K_Node NewList = new K_Node();  
6.     public static void main(String[] args) {          
7.         int Data[][] =          /*圖形陣列宣告*/  
8.             { {1,2,6},{1,6,12},{1,5,10},{2,3,3},{2,4,5},  
9.               {2,6,8},{3,4,7},{4,5,9},{4,6,11},{5,6,1} };  
10.         for(int i = 0 ; i < 10 ; i++ )  
11.         NewList.Create(NewList.FindFree(),Data[i][2],Data[i][0],Data[i][1],0);            
12.           
13.         NewList.printList();  
14.           
15.         System.out.println("K氏法最小擴張樹");  
16.         mintree() ;  
17.         System.out.println("Prim法最小擴張樹");  
18.         findmincost_prim() ;  
19.     }  
20.     //Prim法  
21.     public static int U[]=new int[VERTS+1];//U集合  
22.     public static int V[]=new int[VERTS+1];//V集合  
23.     public static void findmincost_prim()  
24.     {  
25.         //u 已經有1個頂點  
26.         int u = 1 ;  
27.         int count = 1 ;  
28.         int min = 999 , minv = 0 ;  
29.             while(true){  
30.               
31.             for(int v = 0 ; v <VERTS-1; v++){  
32.                 if(NewList.from[v] == u){  
33.                     if(V[NewList.to[v]] == 0 && min > NewList.val[v]){  
34.                           
35.                         min = NewList.val[v] ;  
36.                         minv = v ;  
37.                     }  
38.                 }  
39.             }  
40.             if(count == u){//假設u數量等於count表全部檢查完  
41.             System.out.print("起始頂點["+NewList.from[minv]+"]  終止頂點[");  
42.             System.out.print(NewList.to[minv]+"]  路徑長度["+NewList.val[minv]+"]");  
43.             System.out.println("");       
44.             V[NewList.to[minv]] = 1;//V集合已加入倒U集合  
45.             //U[NewList.to[minv]] = 1;  
46.             count++ ;  
47.             u = 1 ;//找出值後 u重製開開始重新判斷最小值  
48.             min = 999 ; minv = 0 ;  
49.             }else  
50.                 u++ ;    
51.             if(count == U.length-1)//當U數量已飽和跟V一樣  
52.                 break ;  
53.         }  
54.     }  
55.     //K氏法  
56.     public static int findmincost()  
57.     {     
58.         int a=0;  
59.         int minval=100;  
60.         int retptr=0;  
61.         while(NewList.Next[a] !=-1)  
62.         {  
63.             if(NewList.val[a]<minval && NewList.find[a]==0)  
64.             {  
65.                 minval=NewList.val[a];  
66.                 retptr = a ;  
67.             }  
68.             a++ ;  
69.         }  
70.         NewList.find[retptr]=1;//設定已經用過  
71.         return retptr;  
72.     }  
73.     public static void mintree(){  
74.         int pointer = NewList.Header ;  
75.         int retptr=0;//找出最小位置  
76.         int a=0;  
77.         while(pointer  !=-1){  //走訪串列  
78.             retptr = findmincost() ;  
79.             v[NewList.from[retptr]]++ ;  v[NewList.to[retptr]]++ ;  
80.             if(v[NewList.from[retptr]] > 1 && v[NewList.to[retptr]] > 1){           //判斷會不會造成迴路  
81.                 v[NewList.from[retptr]]-- ;  v[NewList.to[retptr]]-- ;  
82.             }else{  
83.                 System.out.print("起始頂點["+NewList.from[retptr]+"]  終止頂點[");  
84.                 System.out.print(NewList.to[retptr]+"]  路徑長度["+NewList.val[retptr]+"]");  
85.                 System.out.println("");       
86.             }  
87.             pointer = NewList.Next[pointer];  
88.         }  
89.     }  
90.   
91. }  
92. class K_Node{  
93.     int Header = 0 ; //起始  
94.     int MaxLength = 20;         // 定義鏈結串列最大長度  
95.     int from[] = new int[MaxLength];//  A  
96.     int to[] = new int[MaxLength];  //    B  
97.     int find[] = new int[MaxLength];      
98.     int val[] = new int[MaxLength]; //長度  
99.     int Next[] = new int[MaxLength];    // 鏈結串列的下一個節點位置  
100.     public K_Node ()                // Node建構子  
101.     {  
102.         for ( int i = 0 ; i < MaxLength ; i++ )  
103.             Next[i] = -2;       // -2表示未用節點  
104.     }  
105.     public void Create(int FreeNode,int DataNum,int fromNum,int toNum,int findNum){  
106.         int pointer ; //現在的節點位置  
107.         if(Header == FreeNode){  
108.             val[Header] = DataNum ;  
109.             from[Header] = fromNum ;  
110.             to[Header] = toNum ;  
111.             find[Header] = findNum ;  
112.             Next[Header] = -1;  
113.         }else{  
114.             pointer = Header;   // 現在的節點為首節點                              
115.             val[FreeNode] = DataNum;// 設定資料編號  
116.             from[FreeNode]=fromNum;  
117.             find[FreeNode]=findNum;  
118.             to[FreeNode]=toNum;  
119.                         // 設定資料名稱  
120.             Next[FreeNode] = -1;    // 將下個節點的位置，-1表示空節點  
121.                         // 找尋鏈結串列尾端  
122.             while ( Next[pointer] != -1)  
123.                 pointer = Next[pointer];  
124.   
125.                         // 將新節點串連在原串列尾端  
126.             Next[pointer] = FreeNode;     
127.   
128.   
129.         }  
130.           
131.           
132.           
133.     }  
134.    public int FindFree(){//搜尋可用節點  
135.        int i ;  
136.        for( i = 0; i < MaxLength ; i++){  
137.            if( Next[i] == -2 )//未使用  
138.                break ;  
139.        }  
140.        return i ;  
141.    }  
142.   public void printList(){  
143.       int pointer = Header ;  
144.       while(pointer != -1){  
145.          System.out.println("邊線 : "+from[pointer] + "-->"+to[pointer]+"      長度 : "+val[pointer] );  
146.          pointer = Next[pointer];  
147.       }  
148.   }  
149.   
150. }