贪婪算法——2 Kruscal算法

/**
 * Kruscal算法求最小生成树<br/>
 * 
 * Kruscal算法把一个加权连通图G=<V,E>最小生成树看作是一个具有V-1条边的无环子图<br/>
 * 
 * 按照权重的非递减顺序对图中的边进行排序，吐过加入的边构成回路，则把该边跳过<br/>
 * <br/>
 * 
 * 并查算法
 * <br/>快速查找：数组  O(n^2)
 * <br/>快速查找：链表 O(nlogn)
 * <br/>快速求并:树   O(n+mlogn)  
 * 
 * @author chenxuegui
 * 
 */
public class Kruscal
{
	// 存放union查找数组
	static List<MyList> list = new ArrayList<>();

	// 存放输入的边
	static List<SideLine> sideLine = new ArrayList<>();

	// 输入的args参数格式[vertex1 vertex2 vertex3...] line [vertexI vertexJ weight]...
	// 其中vertex为a-z的节点
	public static void main(String[] args)
	{
		// 初始化边
		init(args);

		for (int i = 0; list.size() != 1; i++)
		{
			SideLine smallLine = new SideLine(null, null, Integer.MAX_VALUE);

			for (SideLine line : sideLine)
			{
				if (line.getWeight() < smallLine.getWeight())
				{
					smallLine = line;
				}
			}

			sideLine.remove(smallLine);

			// 找出包含smallList中两个节点的两棵树，即链表
			MyList list1 = find(smallLine.getVertex1());

			// 如果list1包含vertex2，说明两个节点在同一棵树中
			if (list1.find(smallLine.getVertex2()))
			{
				continue;
			}

			MyList list2 = find(smallLine.getVertex2());

			union(list1, list2);

		}// end for

		// 输出以验证
		// MyNode node = list.get(0).getFirst();

		System.out.println(list.toString());

	}

	/**
	 * 将两颗树表示的数组队列合并起来
	 * 
	 * @param list1
	 * @param list2
	 */
	private static void union(MyList list1, MyList list2)
	{
		list.remove(list1);
		list.remove(list2);

		System.out.println(list1.toString());
		System.out.println(list2.toString());

		if (list1.getSize() > list2.getSize())
		{
			if (list1.getFirst() == list1.getLast())
			{
				list1.getFirst().setNext(list2.getFirst());
			}
			else
			{
				list1.getLast().setNext(list2.getFirst());
			}

			list1.setLast(list2.getLast());
			list1.setSize(list1.getSize() + list2.getSize());

			list2 = null;
			list.add(list1);
		}
		else
		{
			if (list2.getFirst() == list2.getLast())
			{
				list2.getFirst().setNext(list1.getFirst());
			}
			else
			{
				list2.getLast().setNext(list1.getFirst());
			}
			list2.setLast(list1.getLast());
			list2.setSize(list2.getSize() + list1.getSize());

			list1 = null;
			list.add(list2);
		}

	}

	/**
	 * 将list2连接在list1后面,并将list2从list中移除
	 * 
	 * @param list1
	 * @param list2
	 */
	/*
	 * private static void mergeList(MyList list1, MyList list2) {
	 * list1.getLast().setNext(list2.getFirst());
	 * list1.setLast(list2.getLast());
	 * 
	 * list1.setSize(list1.getSize()+list2.getSize());
	 * 
	 * list.remove(list2); }
	 */

	/**
	 * 在List<MyList>中查找 节点x，返回该MyList
	 * 
	 * @param x
	 * @return
	 */
	private static MyList find(String x)
	{
		MyNode node;

		MyList foundList = null;

		for (MyList myList : list)
		{
			node = myList.getFirst();

			if (myList.find(x))
			{
				foundList = myList;
				break;
			}
		}

		return foundList;
	}

	/**
	 * 从输入的数据中初始化一个SideLine List数组
	 * 
	 * @param args
	 */
	private static void init(String[] args)
	{
		SideLine line;

		MyList myList;

		int i = 0;

		// 初始话list<MyList>
		for (; !args[i].endsWith("line"); i++)
		{

			MyNode n = new MyNode(args[i], null);
			myList = new MyList(1, n, n);
			list.add(myList);

		}

		// 初始化边SideLine
		for (i++; i < args.length; i = i + 3)
		{
			line = new SideLine(args[i], args[i + 1],
					Integer.valueOf(args[i + 2]));
			sideLine.add(line);
		}

	}

}

/**
 * 对边进行封装
 * 
 * @author chenxuegui
 * 
 */
class SideLine
{
	private String vertex1;

	private String vertex2;

	private int weight;

	public SideLine(String vertex1, String vertex2, int weight)
	{
		this.vertex1 = vertex1;
		this.vertex2 = vertex2;
		this.weight = weight;
	}

	public String getVertex1()
	{
		return vertex1;
	}

	public void setVertex1(String vertex1)
	{
		this.vertex1 = vertex1;
	}

	public String getVertex2()
	{
		return vertex2;
	}

	public void setVertex2(String vertex2)
	{
		this.vertex2 = vertex2;
	}

	public int getWeight()
	{
		return weight;
	}

	public void setWeight(int weight)
	{
		this.weight = weight;
	}

}

/**
 * 对同在一客树的节点进行存储，对C中的链表进行模拟
 * 
 * @author chenxuegui
 * 
 */
class MyList
{
	private int size;

	private MyNode first;

	private MyNode last;

	public MyList(int size, MyNode first, MyNode last)
	{
		this.size = size;
		this.first = first;
		this.last = last;
	}

	public String toString()
	{
		String s = "";

		MyNode node = this.first;

		while (node != null)
		{

			s += node.getVertex() + "  ";
			node = node.getNext();
		}

		return s;
	}

	// 在当前MyList中查找节点x，找到时返回true，找不到时返回false
	public boolean find(String x)
	{

		MyNode node = this.first;

		while (node != null && !node.getVertex().equals(x))
		{
			node = node.getNext();
		}

		return node == null ? false : true;
	}

	public int getSize()
	{
		return size;
	}

	public void setSize(int size)
	{
		this.size = size;
	}

	public MyNode getFirst()
	{
		return first;
	}

	public void setFirst(MyNode first)
	{
		this.first = first;
	}

	public MyNode getLast()
	{
		return last;
	}

	public void setLast(MyNode last)
	{
		this.last = last;
	}

}

/**
 * 储存节点的树
 * 
 * @author chenxuegui
 * 
 */
class MyNode
{
	private String vertex;

	private MyNode next;

	public MyNode(String vertex, MyNode next)
	{
		this.vertex = vertex;
		this.next = next;
	}

	public String getVertex()
	{
		return vertex;
	}

	public void setNode(String vertex)
	{
		this.vertex = vertex;
	}

	public MyNode getNext()
	{
		return next;
	}

	public void setNext(MyNode next)
	{
		this.next = next;
	}

}