最小生成树 prim代码,Java代码库,德仔网

代码语言

代码分类

【Java】最小生成树 prim

作者:永泰 / 发布于2016/6/27/ 799

import java.util.*;
 
public class Mintree {
 
    public static void prim(int cl[][], int city[], int length[], int s) {
        int n, i, j;
        int m = 0;
        int k = 0;
        int w = 0;
        n = city.length;
        int v[] = new int[n];
        int front[] = new int[n];// 相邻两节点的前一个节点
        for (i = 0; i < n; i++)
            v[i] = -1; // 初始判断标记 设置为-1
        v[s] = 0;// s被选中 标记改为0
        do {
            int min = 100;// 设置最小值
            int sl = 0; // 设置选取标记 让其等于选取的标签
            int fr = 0;
            for (i = 0; i < n; i++) {
                if (v[i] == -1)
                    continue; // 如果没有选取，就不能找最小边
                for (j = 0; j < n; j++) {
                    if (j != i && cl[i][j] != 0 && cl[i][j] < min && v[j] == -1) {
                        sl = j;
                        fr = i;
                        min = cl[i][j];
                    }
                }
            }
            v[sl] = 0;
            front[w++] = fr;
            city[m++] = sl;
            length[k++] = min;
        } while (city[n - 2] == 0);//例如 7个顶点只用在city存6个数 所以 只判断倒数第二个不为0即可跳出do循环
        for (i = 0; i < n - 1; i++)
            System.out.println(front[i] + "---" + city[i] + "  " + length[i]);
    }
     
    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int n, s;// 设置顶点个数 和起始顶点
        int i, j;
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        int cl[][] = new int[n][n];// 邻接矩阵
        int city[] = new int[n];// 存储从起始点之后选取的顶点
        int length[] = new int[n];// 存储选取最小边的权值
        for (i = 0; i < n; i++)
            for (j = 0; j < n; j++)
                cl[i][j] = sc.nextInt();
        s = sc.nextInt();
        prim(cl, city, length, s);
    }
}

试试其它关键字

　最小生成树prim　

同语言下

可能有用的

永泰贡献的其它代码(12)