Skip to content

Instantly share code, notes, and snippets.

@alexnoz
Created September 5, 2018 21:20
Show Gist options
  • Save alexnoz/88eb0b13c26439b90014d8ba65b70735 to your computer and use it in GitHub Desktop.
Save alexnoz/88eb0b13c26439b90014d8ba65b70735 to your computer and use it in GitHub Desktop.
Minimum spanning tree implementation using Prim's algorithm
#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';
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment