贪婪算法――1 Prim算法

/**
 * Prim 算法构建最小生成树(节点必须含有权重)

 * 
 * 当中每个顶点包含两个标记:(1)指出了最近的树中顶点和边的权重; (2)被选中的顶点和边加粗表示

 * 
 * 加入节点u：

 * (1)把u*从集合V-Vt移动到树的顶点集合Vt中(V为已加入树的节点的集合，Vt为还没加入树的节点的集合)

 * (2)对于集合V-Vt中每一个剩下的顶点u,如果它用一条比u当前距离标记更短的变和u*相连，分别把它的标记更新为u*以及u与u*之间的权重

 * 

 * test: 0 3 0 6 5 3 0 1 0 4 0 1 0 0 4 6 0 0 0 2 5 4 4 2 0






 * test: 0 3 0 0 6 5 3 0 1 0 0 4 0 1 0 6 0 4 0 0 6 0 8 5 6 0 0 8 0 2 5 4 4 5 2 0
 * 
 * 
算法效率：
邻接矩阵,优先队列数组 O(V^2)
 * 
邻接链表,优先队列堆 O(ElogV)
 * @author chenxuegui
 * 
 */
public class Prim
{
	// 节点数
	static int i = 6;

	// 输入5个点的权重举证
	public static void main(String[] args)
	{

		int[][] weight = new int[i][i];

		// 初始化权重矩阵，没有通路的以0表示
		for (int k = 0; k < i * i; k++)
		{
			weight[k / i][k % i] = Integer.valueOf(args[k]);
		}

		// 用hash队列充当优先队列
		Map
  
    map = new HashMap<>();

		// 节点输出的顺序
		List
   
     list = new ArrayList<>(); // 初始化优先队列 for (int k = 0; k < i; k++) { map.put(k, k == 0   -1 : weight[0][k]); } Prim p = new Prim(); p.prim(weight, map, list, i); for (int i : list) { System.out.println(i); } } /** * * 实现prim算法的核心部分，加入权值最小的点 * * @param weight * @param map * @param list * @param i * 节点数 * @param u * 上一个加入节点 */ private void prim(int[][] weight, Map
    
      map, List
     
       list, int i) { for (int k = 0; k < i; k++) { Iterator
      
        it = map.keySet().iterator(); // 取得当前优先队列中最优选择 int minKey = 0; int minValue = Integer.MAX_VALUE; while (it.hasNext()) { int key = it.next(); if (map.get(key) < minValue && map.get(key) != 0) { minValue = map.get(key); minKey = key; } } // 把当前最优点(即距离最短的点)加入list中 list.add(minKey); map.remove(minKey); // 跟新当前优先队列中的点的权值 it = map.keySet().iterator(); while (it.hasNext()) { int key = it.next(); int value = map.get(key); if ((map.get(key) > weight[minKey][key] && weight[minKey][key] != 0) || (map.get(key) == 0)) value = weight[minKey][key]; map.put(key, value); } } } }