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

五菱

import java.util.Scanner;
class Edge {
    /**
     * 边的起点
     */
    char vexa;
    /**
     * 边的终点
     */
    char vexb;
    /**
     * 边的权植
     */
    int weight;
    Edge(char vexa, char vexb, int weight) {
        this.vexa = vexa;
        this.vexb = vexb;
        this.weight = weight;
    }
}
public class MST {
     int n;//图的顶点数
     int m;//图的边数
   
     Edge[] e ;//图的所有边

    public MST(int n,int m,Edge[] e){
      /**
     * 初始化图
     */
      this.n=n;
      this.m=m;
      this.e=e;
     }


    /**
     * w函数
     * @param x 起点序号
     * @param y 终点序号
     * @return 返回起点序号为x，终点序号为y的边的权植。如果没有这条边就返回无穷大
     */
    private int w(int x, int y) {
        char from = (char) (x + 97);
        char to = (char) (y + 97);
        for (int i = 0; i < m; i++) {
            if (e.vexa == from && e.vexb == to) {
                return e.weight;
            }
            if (e.vexa == to && e.vexb == from) {
                return e.weight;
            }
        }
        return 1000; // 用1000代表无穷大，如果图中没有这条边就返回无穷大
    }


    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);   
        while (sc.hasNext()) {   
            int n = sc.nextInt();//图的顶点数
            int m = sc.nextInt();  //图的边数
  
            if (n == 0 && m == 0)   
                break;   
             Edge[] e=new Edge[m];

            for (int i = 0; i < m; ++i) {   
                int u = sc.nextInt();   
                int v = sc.nextInt();   
                int w = sc.nextInt();   
                e=new Edge((char)(u+97),(char)(v+97),w);              
             }   
            MST mst=new MST(n,m,e);

            Edge[] ee =mst.prime();   //存放最小生成树的n-1条边
              
            for (int i = 0; i < n - 1; ++i) {   
                System.out.println(ee.vexa + " " + ee.vexb + " "  
                        + ee.weight);   
            }   
        }   
    }   


     public Edge[] prime(){
        Edge[] e=new Edge[n];//存放最小生成树的n-1条边


        // 表示已经加入最小生成树(mst)的结点, 数组元素从0到n-1分别对应结点a到(char)(n-1+97)
        // 如果vex_mst=0，表示对应结点没有加入到mst
        // 如果vex_mst=1，表示对应结点已经加入到mst
        int[] vex_mst = new int[n];
        for (int i = 0; i < n; i++)
            // 初始化
            vex_mst = 0;
        vex_mst[0] = 1; // 设置初始结点为a
        // 将n-1条边加入到最小生成树
        for (int i = 0; i < n-1; i++) {
            // 加入一条边。
            // 这条边的两个结点一个在mst中，而另一个不在mst中而且具有最小权植
            int add_vex = 0; // 选中的结点
            int min_weight = 1000; // 最小权植,初始值为1000
            Edge adde = new Edge(' ', ' ', 0);
            for (int j = 0; j < n; j++)
                if (vex_mst[j] == 1) { // j是mst中的结点
                    for (int k = 0; k < n; k++) {
                        if (vex_mst[k] == 0 && w(j, k) < min_weight) {
                            add_vex = k;
                            min_weight = w(j, k);
                            adde.vexa = (char) (j + 97);
                            adde.vexb = (char) (k + 97);
                            adde.weight = w(j,k);
                        }
                    }
                }
            vex_mst[add_vex] = 1; // 将选择的结点加入mst
            e=adde;
        }
      
      return e;
    }
}
                    

运行：

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