给出一个ArrayList，里面是Connection类(edge两端的城市名和它们之间的一个cost)，要求找出一些边，把所有城市连接起来并且总花费最小。不能有环，最后所以城市要连成一个连通块。不能的话输出空表或者null(这个不太记得，题目有说，有占一个case)，最后还要按城市名字(先node1，node1相同按node2)排序输出。这题我用了union find + kruskal的做法

原文链接：http://www.jianshu.com/p/1b51aa11e7de

class Connection {
        String city1;
        String city2;
        int cost;
        Connection (String city1, String city2, int cost) {
                this.city1 = city1;
                this.city2 = city2;
                this.cost = cost;
        }

        public void printConnection () {
                System.out.println("{ " + this.city1 + " , " + this.city2 + "} " + this.cost);
        }
}

class Solution {

  public static void main(String[] args) {
                Connection[] citys = new Connection[10];
                citys[0] = new Connection("A","B",6);
                citys[1] = new Connection("A","D",1);
                citys[2] = new Connection("A","E",5);
                citys[3] = new Connection("B","C",3);
                citys[4] = new Connection("B","D",5);
                citys[5] = new Connection("C","D",6);
                citys[6] = new Connection("C","F",6);
                citys[7] = new Connection("D","F",4);
                citys[8] = new Connection("D","E",5);
                citys[9] = new Connection("E","F",2);
                ArrayList<Connection> list = new ArrayList<Connection> ();
                for (Connection temp : citys) {
                        list.add(temp);
                }

                for (Connection temp : findPath(list)){
                        temp.printConnection();
                }

  }

  public static ArrayList<Connection> findPath(ArrayList<Connection> list){

    ArrayList<Connection> res = new ArrayList<Connection>();
    ArrayList<String> cityTree = new ArrayList<String>();
  while(!list.isEmpty()){
//find the minimum cost to the city from cityTree among the result.
     Connection tmp = findMin(list,cityTree);
    if(tmp==null){
    break;
    }
    list.remove(tmp);//remove the current minimum cost from grand set
    cityTree.add(tmp.city1);
    cityTree.add(tmp.city2);
    res.add(tmp);
  }

  //override compare make it alphabet order
    Comparator<Connection> cmp = new Comparator<Connection>(){
    public int compare(Connection a,Connection b){
       if(a.city1.equals(b.city1)){
         return a.city2.compareTo(b.city2);
       }
          return a.city1.compareTo(b.city1);
     }};
          res.sort(cmp);
return res;  
  }

  //Pay Attention!!括号和CityTree和list用的地方别乱
  public static Connection findMin(ArrayList<Connection> list, ArrayList<String> cityTree)   {  
Connection res = null;
     int min = Integer.MAX_VALUE;                                                                       
for(Connection con:list){
         if(con.cost<=min){
             if((cityTree.contains(con.city1)&&!cityTree.contains(con.city2)) ||(!cityTree.contains(con.city1)&& cityTree.contains(con.city2))){
             min = con.cost;
                res = con;
             }
             if(cityTree.isEmpty()){
                min = con.cost;
                res = con;
             }

         }
     }                           
  return res;
  } 
}