// This code is from "Algorithms in Java, Third Edition,"
// by Robert Sedgewick, Addison-Wesley, 2003.

// Program 20.7, priority-first search specialized for MST

// Modified to detect disconnected input graph

class GraphMST
{
  private double[] wt;
  private Edge[] fr, mst;

  private void pfs(Graph G, int s)
  {
    doublePQi pQ = new doublePQi(G.V(), wt);

    pQ.insert(s);
    while (!pQ.empty())
    {
      int v = pQ.getmin();
      mst[v] = fr[v];        
      AdjList A = G.getAdjList(v);
      for (Edge e = A.beg(); !A.end(); e = A.nxt()) 
      {
        double P = e.wt();
        int w = e.other(v);

        if (fr[w] == null)
        {
          wt[w] = P;
          pQ.insert(w);
          fr[w] = e;
        }
        else if (mst[w] == null && P < wt[w])
        {
          wt[w] = P;
          pQ.lower(w);
          fr[w] = e; }
        }
    }
  }

  GraphMST(Graph G)  
  {
    wt = new double[G.V()];
    mst = new Edge[G.V()];
    fr = new Edge[G.V()];

    for (int v = 0; v < G.V(); v++)
      wt[v] = -1.0;
/*
    for (int v = 0; v < G.V(); v++)
      if (mst[v] == null) pfs(G, v);
*/
    pfs(G,0);
    int MSTweight=0;
    for (int v=1;v<G.V();v++)
      if (mst[v]==null)
        System.out.format("Vertex %d not included!\n",v);
      else
      {
        MSTweight+=mst[v].wt();
        System.out.format("MST %s\n",mst[v].toString());
      }
    System.out.format("MST weight %d\n", MSTweight);
  }
}