#include <iostream>
#include <queue>
#include <cstdlib>
#include <vector>

const int MAX = 9;
using namespace std;

class edge {
  public :
    edge(int w, int v1, int v2) : weight(w),vertex1(v1),vertex2(v2){};
    bool operator > (const edge& rhs) const
    {
       return weight > rhs.weight;
    };
   int weight;
   int vertex1;  // in tree
   int vertex2;  // not in tree
   };

void prim(int);  // prims algorithm for finding m.s.t.


int a [MAX][MAX] = {0,6,0,0,0,4,0,0,2,
                    6,0,7,0,9,0,0,0,0,
                    0,7,0,4,3,0,0,0,0,
                    0,0,4,0,0,0,5,1,0,
                    0,9,3,0,0,0,8,0,0,
                    4,0,0,0,0,0,2,0,0,
                    0,0,0,5,8,2,0,0,0,
                    0,0,0,1,0,0,0,0,0,
                    2,0,0,0,0,0,0,0,0 };
                    // example from carrano    13.22

int span [MAX][MAX] = {0};
priority_queue<edge, vector<edge>,greater<edge> > pq;
int main()
{
      prim(0);  // start at vertex 0

      cout << "\nSpanning Tree Matrix" << endl;
      for (int row=0;row<MAX;row++)
      {
        for (int col=0;col<MAX;col++)
          cout << span[row][col];
        cout << endl;
      }
      cout <<"\n Spanning Tree"<<endl;
      for (int row=0;row<MAX;row++)
        for (int col=0;col<row;col++)
          if ( span[row][col] > 0)
             cout << row << " ----(" << span[row][col] << ")---- " << col << endl;

      cout << endl;
      system("pause");
      return 0;
}

void printpq()
{
    cout << "displaying pq " << endl;
    while (!pq.empty())
    {
       cout << pq.top().weight << " v " << pq.top().vertex1<< " u " << pq.top().vertex2<<endl;
       pq.pop();
    }
}

// prims algorithm from carrano implemented using priority queue
    void prim(int v)
    {
         int u;
         bool inTree[]={false,false,false,false,false,false,false,false,false};
         inTree[v] = true;
         // push all v's weighted edges onto pq
         for (int i=0; i< MAX;i++)
             if (a[v][i]>0)
                  pq.push(edge(a[v][i],v,i));
 
         // pq contains the weighted edges of all inTree vertices       
         // i.e. each vertex1 is in tree (inTree)
         while ( !pq.empty()) 
         {
             edge minedge = pq.top();
             pq.pop();
             u=minedge.vertex2;
             v=minedge.vertex1; // vertex1 MUST be in tree
             if (!inTree[u])
             {
                 inTree[u] = true;
                 // add u to spanning tree
                 span[v][u] = a[v][u];
                 span[u][v] = a[u][v];
                 // push all u's edges to vertices not in tree onto priority queue
                 for (int i=0; i< MAX;i++)
                    if (a[u][i]>0 && !inTree[i])
                       pq.push(edge(a[u][i],u,i));
              }
         }
        

   }