Minimum spanning tree implementation using Prim's algorithm

mst.cpp

#include <iostream>
#include <vector>
#include <array>
#include <climits> // INT_MAX
#include <algorithm> // find

using std::vector;

using edges_t = vector<std::array<int, 2>>;
using graph_t = vector<edges_t>;

struct Node {
  int p = -1;
  int d = INT_MAX;
};

template <typename T>
bool contains(const vector<T>& vec, T val) {
  return std::find(vec.begin(), vec.end(), val) != vec.end();
}

// This ideally should be priority_queue
int findMinVertex(const vector<Node>& nodes, const vector<int>& seen) {
  int minVal = INT_MAX, minV;

  for (int i = 0; i < nodes.size(); ++i) {
    if (!contains(seen, i) && nodes[i].d < minVal) {
      minVal = nodes[i].d;
      minV = i;
    }
  }

  return minV;
}

edges_t minimumSpanningTree(const graph_t& graph, int src) {
  const int len = graph.size();
  vector<Node> nodes(len);
  
  // Initialization
  for (int i = 0; i < len; ++i) {
    nodes[i] = Node();
  }
  
  nodes[src].d = 0;

  vector<int> seen;

  while (seen.size() < len) {
    const int u = findMinVertex(nodes, seen);
    
    seen.push_back(u);

    edges_t adjacent = graph[u];

    for (const auto& edge : adjacent) {
      int v = edge[0]; // Adjacent vertex
      int w = edge[1]; // Weight
  
      if (!contains(seen, v) && nodes[v].d > w) {
        nodes[v].d = w;
        nodes[v].p = u;
      }
    }
  }

  edges_t mst(graph.size());

  for (int i = 0; i < nodes.size(); ++i) {
    mst[i] = {i, nodes[i].p};
  }

  return mst;
}

int main() {
  graph_t graph(9, edges_t(4));
  
  graph[0] = {{1, 4}, {7, 8}};
  graph[1] = {{0, 4}, {2, 8}, {7, 11}};
  graph[2] = {{1, 8}, {3, 7}, {5, 4}, {8, 2}};
  graph[3] = {{2, 7}, {4, 9}, {5, 14}};
  graph[4] = {{3, 9}, {5, 10}};
  graph[5] = {{4, 10}, {3, 14}, {2, 4}, {6, 2}};
  graph[6] = {{5, 2}, {7, 1}, {8, 6}};
  graph[7] = {{6, 1}, {8, 7}, {0, 8}, {1, 11}};
  graph[8] = {{2, 2}, {6, 6}, {7, 7}};

  const edges_t mst = minimumSpanningTree(graph, 0);

  for (const auto& edge : mst) {
    std::cout << edge[0] << " - " << edge[1] << '\n';
  }
}