Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- public Iterator<E> minimumSpanningTree() {
- DirectedGraph cc = new DirectedGraph(size);
- List<E>[] mstList = cc.lists;
- int nbrOfNotConnected = size;
- PriorityQueue<CompKruskalEdge<E>> kruskPq = new PriorityQueue<CompKruskalEdge<E>>();
- for(List<E> tmpList: lists){
- for(E ex: tmpList){
- kruskPq.add(new CompKruskalEdge<E>(ex));
- }
- }
- while(!kruskPq.isEmpty() && nbrOfNotConnected > 1){
- CompKruskalEdge<E> e = kruskPq.poll();
- if(!(mstList[e.getFrom()] == mstList[e.getTo()])){
- List<E> longestList = mstList[e.getFrom()];
- List<E> shortestList = mstList[e.getTo()];
- if(shortestList.size() > longestList.size()){
- List<E> tmpList = shortestList;
- shortestList = longestList;
- longestList = tmpList;
- }
- for(E f: shortestList){
- longestList.add(f);
- }
- longestList.add(e.getEdge());
- for(E g: shortestList){
- mstList[g.from] = longestList;
- mstList[g.to] = longestList;
- }
- mstList[e.getFrom()] = longestList;
- mstList[e.getTo()] = longestList;
- }
- }
- return mstList[0].iterator();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement