Go语言视频零基础入门到精通

javalearner

1. [img]http://img.javaxxz.com/2014/12/1/000548531.jpg[/img]
2. 
   
3. import java.util.Scanner;
   
4. class Edge {
   
5.     /**
   
6.      * 边的起点
   
7.      */
   
8.     char vexa;
   
9.     /**
   
10.      * 边的终点
    
11.      */
    
12.     char vexb;
    
13.     /**
    
14.      * 边的权植
    
15.      */
    
16.     int weight;
    
17.     Edge(char vexa, char vexb, int weight) {
    
18.         this.vexa = vexa;
    
19.         this.vexb = vexb;
    
20.         this.weight = weight;
    
21.     }
    
22. }
    
23. public class MST {
    
24.      int n;//图的顶点数
    
25.      int m;//图的边数
    
26.    
    
27.      Edge[] e ;//图的所有边
    
28. 
    
29.     public MST(int n,int m,Edge[] e){
    
30.       /**
    
31.      * 初始化图
    
32.      */
    
33.       this.n=n;
    
34.       this.m=m;
    
35.       this.e=e;
    
36.      }
    
37. 
    
38. 
    
39.     /**
    
40.      * w函数
    
41.      * @param x 起点序号
    
42.      * @param y 终点序号
    
43.      * @return 返回起点序号为x，终点序号为y的边的权植。如果没有这条边就返回无穷大
    
44.      */
    
45.     private int w(int x, int y) {
    
46.         char from = (char) (x + 97);
    
47.         char to = (char) (y + 97);
    
48.         for (int i = 0; i < m; i++) {
    
49.             if (e[i].vexa == from && e[i].vexb == to) {
    
50.                 return e[i].weight;
    
51.             }
    
52.             if (e[i].vexa == to && e[i].vexb == from) {
    
53.                 return e[i].weight;
    
54.             }
    
55.         }
    
56.         return 1000; // 用1000代表无穷大，如果图中没有这条边就返回无穷大
    
57.     }
    
58. 
    
59. 
    
60.     public static void main(String[] args) {
    
61. 
    
62.         Scanner sc = new Scanner(System.in);   
    
63.         while (sc.hasNext()) {   
    
64.             int n = sc.nextInt();//图的顶点数
    
65.             int m = sc.nextInt();  //图的边数
    
66.   
    
67.             if (n == 0 && m == 0)   
    
68.                 break;   
    
69.              Edge[] e=new Edge[m];
    
70. 
    
71.             for (int i = 0; i < m; ++i) {   
    
72.                 int u = sc.nextInt();   
    
73.                 int v = sc.nextInt();   
    
74.                 int w = sc.nextInt();   
    
75.                 e[i]=new Edge((char)(u+97),(char)(v+97),w);              
    
76.              }   
    
77.             MST mst=new MST(n,m,e);
    
78. 
    
79.             Edge[] ee =mst.prime();   //存放最小生成树的n-1条边
    
80.               
    
81.             for (int i = 0; i < n - 1; ++i) {   
    
82.                 System.out.println(ee[i].vexa + " " + ee[i].vexb + " "  
    
83.                         + ee[i].weight);   
    
84.             }   
    
85.         }   
    
86.     }   
    
87. 
    
88. 
    
89.      public Edge[] prime(){
    
90.         Edge[] e=new Edge[n];//存放最小生成树的n-1条边
    
91. 
    
92. 
    
93.         // 表示已经加入最小生成树(mst)的结点, 数组元素从0到n-1分别对应结点a到(char)(n-1+97)
    
94.         // 如果vex_mst[i]=0，表示对应结点没有加入到mst
    
95.         // 如果vex_mst[i]=1，表示对应结点已经加入到mst
    
96.         int[] vex_mst = new int[n];
    
97.         for (int i = 0; i < n; i++)
    
98.             // 初始化
    
99.             vex_mst[i] = 0;
    
100.         vex_mst[0] = 1; // 设置初始结点为a
     
101.         // 将n-1条边加入到最小生成树
     
102.         for (int i = 0; i < n-1; i++) {
     
103.             // 加入一条边。
     
104.             // 这条边的两个结点一个在mst中，而另一个不在mst中而且具有最小权植
     
105.             int add_vex = 0; // 选中的结点
     
106.             int min_weight = 1000; // 最小权植,初始值为1000
     
107.             Edge adde = new Edge(" ", " ", 0);
     
108.             for (int j = 0; j < n; j++)
     
109.                 if (vex_mst[j] == 1) { // j是mst中的结点
     
110.                     for (int k = 0; k < n; k++) {
     
111.                         if (vex_mst[k] == 0 && w(j, k) < min_weight) {
     
112.                             add_vex = k;
     
113.                             min_weight = w(j, k);
     
114.                             adde.vexa = (char) (j + 97);
     
115.                             adde.vexb = (char) (k + 97);
     
116.                             adde.weight = w(j,k);
     
117.                         }
     
118.                     }
     
119.                 }
     
120.             vex_mst[add_vex] = 1; // 将选择的结点加入mst
     
121.             e[i]=adde;
     
122.         }
     
123.       
     
124.       return e;
     
125.     }
     
126. }
     
127.                                        
     

复制代码

运行： C:aaa>java MST
5 8
0 1 2
1 4 9
4 3 7
3 0 10
0 2 12
2 4 3
1 2 8
2 3 6

a b 2
b c 8
c e 3
c d 6
0 0
  
   
     
     
      
      

        
      

        
      
     
   

  


源码下载：http://file.javaxxz.com/2014/12/1/000548890.zip