public static WUGraph minSpanTree(WUGraph g){

  	// 1: Create new graph t having the same vertices as G, but no edges yet.

    WUGraph t = new WUGraph();

  	for (Object item : g.getVertices()) {
    	t.addVertex(item);
	  }

  	// 2: Make a list of all edges in G by calling multiple times getNeighbors()

  	Object[] verticesList = t.getVertices();

    LinkedQueue queue = new LinkedQueue();

    for(int i = 0; i < t.vertexCount(); i++){
      Neighbors neighbor = g.getNeighbors(verticesList[i]);      
      for (int j = 0; j < neighbor.neighborList.length; j++){
        Object v1 = verticesList[i];
        Object v2 = neighbor.neighborList[j];
        int w = g.weight(v1, v2);
        Edge edge = new Edge(v1, v2, w);     
        queue.enqueue(edge);
      }
    }
 

  	// 3: Sort the edges by weight in O(E*log(E)) time

    mergeSort(queue);
    
  	// 4: Finally, find the edges of the minimun spanning tree t using disjoint sets.

    int queueSize = queue.size();
    DisjointSets ds = new DisjointSets(t.vertexCount());
    HashTableChained hashTable = new HashTableChained(t.vertexCount());

    
    //Insert the vertices in the hashtable. The hashCode will be its position in
    // the verticesList list.
    int index = 0;

    for (Object v : verticesList){
      hashTable.insert(v, index);
      index++;
    }

    //Iterate over the edges in the queue, adding them if the vertices of the edge
    // belong to different sets
    for (int i = 0; i < queueSize; i++){
      try{
        Edge ed = (Edge) queue.dequeue();
        Object vertex1 = ed.getVertex1();
        Object vertex2 = ed.getVertex2();
        int v1 = (Integer) hashTable.find(vertex1).value();
        int v2 = (Integer) hashTable.find(vertex2).value();
        if (ds.find(v1) == ds.find(v2)){
        } else {
          t.addEdge(ed.getVertex1(), ed.getVertex2(), ed.getWeight());
          ds.union(ds.find(v1),ds.find(v2));
        }
      } catch (QueueEmptyException e){}
    }

    return t;

	}