SpanningTree.java

package graphs;

import java.util.Comparator;
import java.util.PriorityQueue;

public class SpanningTree {
	private Double[] distances;
	private WeightedGraph graph;

	boolean debug = true;

	public class VertexEdgeComparator implements Comparator<Integer> {

		@Override
		public int compare(Integer o1, Integer o2) {

			double minFirst = getMin(o1);
			double minSecond = getMin(o2);
			if (minFirst > minSecond) {
				return 1;
			} else if (minFirst == minSecond) {
				return 0;
			} else {
				return -1;
			}

		}

		private double getMin(Integer o1) {
			double maxFirst = Double.MAX_VALUE;
			for (Integer v : graph.adj(o1)) {
				if (maxFirst < graph.getWeight(o1, v)) {
					maxFirst = graph.getWeight(o1, v);
				}
			}
			return maxFirst;
		}

	}

	public Graph spanningTree(int source) {
		if (source < 0 || source >= graph.V()) {
			throw new IndexOutOfBoundsException();
		}

		Graph g = new Graph(graph.V());

		for (int u = 0; u < graph.V(); u++) {

		}

		PriorityQueue<Integer> q = new PriorityQueue<Integer>(graph.V(), new VertexEdgeComparator());
		for (int i = 0; i < graph.V(); i++) {
			q.add(i);
		}

		while (!q.isEmpty()) {
			Integer u = q.poll();

			for (Integer v : graph.adj(u)) {
				if (q.contains(v) && graph.getWeight(u, v) < distances[v]) {
					distances[v] = graph.getWeight(u, v);
					g.addUndirectedEdge(u, v);
				}
			}

			if (debug) {
				System.out.println(this);
			}
		}

		return g;

	}
	
	
	public static void main(String[] args) {
		
	}

}