# Xavier Geerinck

My thoughts, tutorials and learnings

June 5, 2015 - algorithms cpp

# Prim's Algorithm

Xavier Geerinck

@XavierGeerinck

## Did you enjoy reading? Or do you want to stay up-to-date of new Articles?

Consider sponsoring me or providing feedback so I can continue creating high-quality articles!

Prim's algorithm solves problems such as finding the Minimum Spanning Tree (MST) of a graph. With a MST we mean the solution set that connects every node of a graph together with the least weight.

let's say for example that you want to every major city of Mexico but by driving the least kilometers, this particular problem can be solved by using prim's algorithm to determining the path.

## Used Graph

For this example I will be using the following graph:

The first thing we have to do when working with graphs is to convert them into their list or matrix view depending on the implementation. I have chosen to solve this problem by using a Matrix so let's use this.

Matrix View:

`[ 0, 2, 4, 0 ][ 2, 0, 1, 5 ][ 4, 1, 0, 3 ][ 0, 5, 3, 0 ]`

This matrix view shows the weights from one node to the other.

## Prim's Algorithm

### General

Prim's Algorithm starts by picking the smallest node key value. Once we have that one we will look at the neighbours that connects to the current subgraph. Now we will pick the smallest neighbour and add this to our subgraph.

We keep performing this process until everything is connected, also bear in mind that we can not have loops in the graph!

After performing this on a sheet of paper we get the following result:

1 -> 2 -> 3 -> 4

### Pseudocode

`// Algorithm:// 1) Init a priority queue, visited list and solution vector// 2) Put every element on visited = false// 3) Pick a start element and put it on the priority queue// 4) while !Q.empty//  4a) Get next unvisited nodewhile (visited[Q.top()] && !Q.empty()) {  Q.pop();  // Set unvisited node as visited and add it to the solution  if (!pq.empty())    p = Q.pop();    visited[p] = true;    mst.push_back(p);  for (neighbour r in grap) {    if (graph.weight[r] != 0 && !visited[r]) {      Q.push(r);    }  }}// Return solutionreturn mst;`

### C++ Implementation

`#include#include#includeusing namespace std;struct node {  int key;  int weight;};bool operator<(const node& a, const node& b) { return a.weight > b.weight; }template void print_list(vector numbers) {  for (auto i = 0; i < numbers.size(); i++) {    cout << numbers[i] << " ";  }  cout << endl;}vector prim(vector<vector> &graph) {  // Init priority queue and parents  vector visited(graph.size(), false);  vector mst; // solution  priority_queue pq;  struct node start;  start.key = 0;  start.weight = 0;  pq.push(start);  while (!pq.empty()) {    // Get next unvisited node    while (visited[pq.top().key] && !pq.empty()) {      pq.pop();    }    if (!pq.empty()) {      struct node curr_node = pq.top();      visited[curr_node.key] = true; // set it visited (black)      mst.push_back(curr_node.key); // Add it to the solution      pq.pop();      // Get the neighbours of the current node      // Neighbours are all X values that are not 0 in graph[curr_node.key][X] and not visited      for (int i = 0; i < graph.size(); i++) {        if (graph[curr_node.key][i] != 0 && !visited[i]) {          struct node node;          node.key = i;          node.weight = graph[curr_node.key][i];          pq.push(node);        }      }    }  }  return mst;}int main(int argc, const char * argv[]) {  vector<vector> graph;  graph = {    { 0, 2, 4, 0 },    { 2, 0, 1, 5 },    { 4, 1, 0, 3 },    { 0, 5, 3, 0 }  };  // Print solution  print_list(prim(graph));  return 0;}`

## Did you enjoy reading? Or do you want to stay up-to-date of new Articles?

Consider sponsoring me or providing feedback so I can continue creating high-quality articles!