Advertisement
Guest User

Untitled

a guest
Mar 4th, 2015
215
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.09 KB | None | 0 0
  1.  
  2. public Iterator<E> minimumSpanningTree() {
  3. DirectedGraph cc = new DirectedGraph(size);
  4. List<E>[] mstList = cc.lists;
  5. int nbrOfNotConnected = size;
  6. PriorityQueue<CompKruskalEdge<E>> kruskPq = new PriorityQueue<CompKruskalEdge<E>>();
  7. for(List<E> tmpList: lists){
  8. for(E ex: tmpList){
  9. kruskPq.add(new CompKruskalEdge<E>(ex));
  10. }
  11. }
  12. while(!kruskPq.isEmpty() && nbrOfNotConnected > 1){
  13. CompKruskalEdge<E> e = kruskPq.poll();
  14. if(!(mstList[e.getFrom()] == mstList[e.getTo()])){
  15. List<E> longestList = mstList[e.getFrom()];
  16. List<E> shortestList = mstList[e.getTo()];
  17.  
  18. if(shortestList.size() > longestList.size()){
  19. List<E> tmpList = shortestList;
  20. shortestList = longestList;
  21. longestList = tmpList;
  22. }
  23.  
  24. for(E f: shortestList){
  25. longestList.add(f);
  26. }
  27. longestList.add(e.getEdge());
  28. for(E g: shortestList){
  29. mstList[g.from] = longestList;
  30. mstList[g.to] = longestList;
  31. }
  32. mstList[e.getFrom()] = longestList;
  33. mstList[e.getTo()] = longestList;
  34. }
  35. }
  36.  
  37. return mstList[0].iterator();
  38. }
  39. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement