MST

mst.c

#include <stdio.h>
#include <vector>

using namespace std;

int num_vertices;

// this vector is for the adjacency matrix
vector <vector <int> > adj_matrix;

// this vector is the the getting data in each of the rows,
// then inserting the row the in the 2d adj_matrix;
vector <int> tmp_row;

// use this int to scanf all the data one by one for the rows
int tmp;

// we will use this vector for the set calculation
vector <int> sets;

// we check the adjacency matrix, and then find the min cost edge
// when we find it, we mark it as visited, so that we never get it's
// value when we try to find the second minimum and so on
vector < vector <int> > visited;

// this variables are used to keep the min edge value
int min_edge_u;
int min_edge_v;
int min_edge_cost;

// this is where we save mst
vector <vector <int> > mst;

// cost for the mst
int mst_cost = 0;


void get_input(){
    printf("First you need to provide the input graph\n");
    printf("Provide the number of vertices\n");
    scanf("%d", &num_vertices);
    for(int i = 0; i <  num_vertices; i++){
    	// make sure the vector is free
    	// we do not want any data from previous rows
		tmp_row.clear();

		for (int j = 0; j < num_vertices; j++){
			scanf("%d", &tmp);

			// put tmp in tmp_row
			tmp_row.push_back(tmp);
		}

		// put tmp_row into adj_matrix
		adj_matrix.push_back(tmp_row);
    }
}

void print_input(){
	printf("Printing the input graph\n");
	for(int i = 0; i < num_vertices; i++){
		for(int j = 0; j < num_vertices; j++){
			printf("%d ", adj_matrix[i][j]);
		}
		printf("\n");
	}
}

void create_initial_set(){
	for(int i = 0; i < num_vertices; i++){
		// vertex at index i will be assigned set no i
		sets.push_back(i);
	}
}

// merge the set of vertex u and v, merged set will have the value of
// set of vertex u
void merge_set(int u, int v){
	int set_u = sets[u];
	int set_v = sets[v];
	for(int i = 0; i < num_vertices; i++){
		if (sets[i] == set_v)
			sets[i] = set_u;
	}
}

void mark_all_unvisited(){
	visited.clear();
	for(int i = 0; i < num_vertices; i++){
		tmp_row.clear();
		for(int j = 0; j < num_vertices; j++){
			// 0 means unvisited
			tmp_row.push_back(0);
		}
		visited.push_back(tmp_row);
	}
}

void find_min_edge(){
	min_edge_cost = INT_MAX;
	min_edge_u = -1;
	min_edge_v = -1;

	for(int i = 0; i < num_vertices; i++){

		for(int j = 0; j < num_vertices; j++){

		if (visited[i][j] == 0){

			if(adj_matrix[i][j] > 0 && adj_matrix[i][j] < min_edge_cost){

				min_edge_cost = adj_matrix[i][j];
				min_edge_u = i;
				min_edge_v = j;

				}
			}
		}
	}

	if (min_edge_cost < INT_MAX){
		visited[min_edge_u][min_edge_v] = 1;
		visited[min_edge_v][min_edge_u] = 1;

		printf("Min Edge found between vertex %d and %d with cost %d \n", min_edge_u, min_edge_v, min_edge_cost);
	}
}

void create_emtpy_mst(){
	mst.clear();
	for(int i = 0; i < num_vertices; i++){
		tmp_row.clear();
		for(int j = 0; j < num_vertices; j++){
			// 0 means unvisited
			tmp_row.push_back(0);
		}
		mst.push_back(tmp_row);
	}
}


void print_mst(){
	printf("Printing the mst\n");
	for(int i = 0; i < num_vertices; i++){
		for(int j = 0; j < num_vertices; j++){
			printf("%d ", mst[i][j]);
		}
		printf("\n");
	}
}

int main(){
	// get input from users
	get_input();

	// print input
	print_input();

	// create initial sets
	create_initial_set();

	// mark all edges as visited
	mark_all_unvisited();

	// create empty mst
	create_emtpy_mst();

	// main algo
	do{
		// find the current minimum cost edge
		find_min_edge();

		// check the sets of the vertex of the min edge
		if(sets[min_edge_u] != sets[min_edge_v]){
			// they are from different sets, so add this edge to MST
			printf("Different Forrest, Merging Sets for %d and %d\n", min_edge_u, min_edge_v);

			// code for MST
			mst[min_edge_u][min_edge_v] = 1;
			mst[min_edge_v][min_edge_u] = 1;
			mst_cost += min_edge_cost;

			// merge those sets
			merge_set(min_edge_u, min_edge_v);
		}else{
			printf("Same forest, not merging for %d and %d\n", min_edge_u, min_edge_v);
		}
	}while(min_edge_cost != INT_MAX);

	// print mst using bfs
	print_mst();

	// print min cost
	printf("The cost of the MST: %d\n", mst_cost);


}