贪心算法(四)——最小代价生成树

/**
 * @param a：图的邻接矩阵
 */
EdgeSet spanningTree(int[][] a){
    // 结果集（边的集合）
    EdgeSet solution = new EdgeSet();
    // 选出n-1条边
    int i = 0;
    while( i<n && 还有未检查的边 ){
        // 选出一条边
        Edge edge = Select(a);
        // 判断是否有回路
        if ( !hasLoop(edge) ) {
            solution.add( edge );
        }
    }
    return solution;
}

/**
 * 边节点（由一条边和一个终止节点构成）
 */
class ENode{
    int id;// 终止节点的编号
    int weight;// 边的权重
}

Map<String,List<ENode>>

/**
 * prim算法
 * @param graph:图的邻接矩阵
 */
void prim(Map<String,List<Edge>> graph){
    // 初始化
    Map<String,String> nearest = new HashMap<>();
    Map<String,Integer> lowcost = new HashMap<>();
    Map<String,Boolean> mark = new HashMap<>();
    String k = null;
    String end = null;// 记录最后一个节点的id，用于从后向前输出结果

    for( String id : graph.keySet() ){
        nearest.put( id, null );
        lowcost.put( id, Integer.MAX_VALUE );
        mark.put( id, false );
        k = id;
    }
    mark.put( id, true );

    // 寻找生成树的n-1条边
    for(int i=1; i<=graph.size()-1; i++){

        // 更新与k相邻的nearest
        List<ENode> edges = graph.get( k );
        for( ENode edge : edges ){
            if ( !mark.get(edge.id) && edge.w < lowcost.get(edge.id) ) {
                lowcost.put( edge.id, edge.w );
                nearest.put( edge.id, k );
            }
        }

        // 寻找当前lowcost中最短的边
        int min = Integer.MAX_VALUE;
        for( Map.Entry<String,Integer> entry : lowcost.entrySet() ){
            if ( entry.getValue() < min ) {
                min = entry.getValue();
                k = entry.getKey();
            }
        }
        mark.get( k, true );
        end = k;
    }

    // 输出结果
    for ( int i=0; i<graph.size(); i++ ) {
        System.out.println( nearest.get(end)+"-"+end+"权值："+lowcost.get(end) );
        end = nearest.get(end);
    }
}