public LazyPrimMST(EdgeWeightedGraph G)
	{
		pq = new PriorityQueue<WeightedEdge>();
		mst = new LinkedList<WeightedEdge>();
		marked = new boolean[G.V()];

		// Determine the initial candidates w.r.t. the vertex 0
		// The candidates are inserted into pq
		visit(G, 0);
		while (!pq.isEmpty())
		{
			// Remove the edge with the smallest weight from among the
			// candidates
			WeightedEdge e = pq.remove();
			int v = e.either(), w = e.other(v);

			// Lazy exclusion of ineligible edges(edges already in the mst) from
			// the candidates
			// Note that these edges were eligible when they were selected as
			// candidates as one of their vertices was a non-mst vertex. They
			// have in due course of adding other edges to the mst become
			// ineligible as they now connect vertices in the mst

			// Is the edge already on the mst?
			// Would have been more intuitive if the mst had been a ST instead
			// of a bag. Could have done a mst.exists(). This is more efficient
			// though
			if (marked[v] && marked[w])
				continue;

			// Add e to the mst
			mst.add(e);
			weight += e.weight();

			// Visit the neighbouring vertices to discover the fresh candidates
			// now that a new edge has been added to the MST
			if (!marked[v])
				visit(G, v);
			if (!marked[w])
				visit(G, w);
		}
	}