/*
 * Michael Gousie
 * COMP 318  Spring 2026
 * prims.cpp
 *
 * Prim's Algorithm
 * Implemented with the graph shown in class.
 *
 */

#include<iostream>
using namespace std;

const int V = 10;    // set max number of vertices

int G [V][V] = {     // set up adjacency matrix; 0 represents no edge
	{0, 3, 0, 4, 4, 0, 0, 0, 0, 0},   // from A
	{3, 0, 10, 0, 2, 3, 0, 0, 0, 0},  // from B
	{0, 10, 0, 0, 0, 6, 1, 0, 0, 0},  // from C
	{4, 0, 0, 0, 5, 0, 0, 6, 0, 0},   // from D
	{4, 2, 0, 5, 0, 11, 0, 2, 1, 0},  // from E
	{0, 3, 6, 0, 11, 0, 2, 0, 3, 11}, // from F
	{0, 0, 1, 0, 0, 2, 0, 0, 0, 8},   // from G
	{0, 0, 0, 6, 2, 0, 0, 0, 4, 0},   // from H
	{0, 0, 0, 0, 1, 3, 0, 4, 0, 7},   // from I
	{0, 0, 0, 0, 0, 11, 8, 0, 7, 0}   // from J
};

int main () {
   int numEdges = 0; // number of edges processed
   bool Vt [V];      // vertex array storing visited nodes
   int i, j;         // loopers
   int row, col;     // row, column
   int minEdge;      // minimum weight edge

   for (i = 0; i < V; i++)
      Vt[i] = false;	// no nodes have been visited

   // start with vertex A = 0
   Vt [0] = true;
   while (numEdges < V - 1) {     // need V-1 edges to connect all V nodes
      minEdge = 9999;		  // maximum possible weight (careful here!)
      
      // look through each vertex, starting at A (0)
      for (i = 0; i < V; i++) {
         if (Vt[i]) {
            // find nodes connected to node i
            for (j = 0; j < V; j++) {
               if (!Vt[j] && G[i][j]) {   // an edge exists between i and j
                  if (G[i][j] < minEdge) {
                     minEdge = G[i][j];
                     row = i;
                     col = j;
                  }
               }
            }
         }
      }

      // show found edge
      cout << row << " - " << col << "  " << G[row][col] << endl;
      Vt[col] = true;
      numEdges++;
   }

   return 0;
}