void Prim(Graph* G, int* D, int s) {
 	int V[G->n()];
	int i, w;
   for (i=0; i<G->n(); i++) { 
     int v = minVertex(G, D);
     G->setMark(v, VISITED);
     if (v != s) AddEdgetoMST(V[v], v); 
     if (D[v] == INFINITY) return;
     for (w=G->first(v); w<G->n(); 
		w=G->next(v,w))
       if (D[w] > G->weight(v,w)) {
         D[w] = G->weight(v,w); 
         V[w] = v; 
       }
   }
}

int minVertex(Graph* G, int* D) {
  int j, v;
  for (j=0; j<G->n(); j++)
     if (G->getMark(j) == UNVISITED)
     { v = j; break; }
  for (j++; j<G->n(); j++)
	 if ((G->getMark(j) == UNVISITED) 
		&& (D[j] < D[v]))
        v = j;
  return v;
}


class Graph { // Graph abstract class
public:
  virtual int n() =0; // # of vertices for whole graph
  virtual int e() =0; // # of edges for whole graph
  // Return index of first neighbor for a given vertex 
  virtual int first(int) =0;
  // Return index of next neighbor (get vertex1’s neighbor after         // vertex2).
	virtual int next(int, int) =0;
  // Store new edge, identified by two vertices, 3rd parm is weight
  virtual void setEdge(int, int, int) =0;
  // Delete edge defined by two vertices
  virtual void delEdge(int, int) =0;
  // Weight of edge connecting two vertices
  virtual int weight(int, int) =0;
 	// The mark functions are used for traversal (VISITED or not)
  virtual int getMark(int) =0;
	virtual void setMark(int, int) =0;
};

int V[G->n()];

#include <iostream>
#include<math.h>

using namespace std;

int matrix[50][50];
int finishedWeight[50];
int finishedVertices[50];
char* edges[50];
int counter = 0;
int size = 0;

void fillMatrix(int vertexNum)
{
  for(int i = 0; i < vertexNum; i++)
  {
    for(int j = 0; j < vertexNum; j++)
    {
      matrix[i][j] = pow(2,32) - 1;
    }
  }
}

void insert(int start, int end, int weight)
{
    matrix[start][end] = weight;
}

void addUndirected(int vertexNum)
{
  int start = 0;
  int end = 0;
  int weight;
  size = vertexNum;
  
  fillMatrix(vertexNum);
  while(start != -1)
  {
    cout << "Please enter a starting vertex: ";
    cin >> start;
    cout << "Please enter an ending vertex: ";
    cin >> end;
    cout << "Please enter a weight: ";
    cin >> weight;
    insert(start, end, weight);
    insert(end, start, weight);
  } 

  for(int i = 0; i < vertexNum; i++)
  {
    for(int j = 0; j < vertexNum; j++)
    {
      cout << "matrix[" << i << "][" << j << "] = " << matrix[i][j] << endl;
    }
  }
}

void addDirected(int vertexNum)
{
  int start = 0;
  int end = 0;
  int weight;
  size = vertexNum;
  fillMatrix(vertexNum);
  while(start != -1)
  {
    cout << "Please enter a starting vertex: ";
    cin >> start;
    cout << "Please enter an ending vertex: ";
    cin >> end;
    cout << "Please enter a weight: ";
    cin >> weight;
    insert(start, end, weight);
  }

  for(int i = 0; i < vertexNum; i++)
  {
    for(int j = 0; j < vertexNum; j++)
    {
      cout << "matrix[" << i << "][" << j << "] = " << matrix[i][j] << endl;
    }
  }
} 


void prim(int startingVertex)
{
  cout << "Size = " << size << endl;
  int start = startingVertex;
  int end;
  int weight;
  int minx;
  int miny;
  int minWeight = pow(2, 32) - 1;
  for(int k = 0; k < size; k++)
  {
    finishedVertices[k] = start;
    for(int l = 0; l < size; l++)
    {
      if(matrix[start][l] < minWeight)
      {
        for(int i = 0; i < size; i++)
	{
	   if(matrix[start][l] != finishedWeight[i])
	   {
	     minx = start;
             miny = l;
             minWeight = matrix[minx][miny];
	   }
	 }
      }
    }
  }
  finishedVertices[counter] = minx;
  cout << "finished vertices at 0 = " << finishedVertices[0] << endl;
  cout << "finished vertices at 1 = " << finishedVertices[1] << endl;
  finishedWeight[counter] = minWeight;
  cout << "FinishedWeight at 0 = " << finishedWeight[0] << endl;
  cout << "finishedWeight at 1 = " << finishedWeight[1] << endl;
  counter++;
  if(counter != size)
    prim(2);  //note: just to see if it would work with something else     
}

int main()
{
  addDirected(5);
  int  option;
  cout << "Please enter a starting vertex: ";
  cin >> option;
  prim(option);
  return 0;
}