New Start Day 10: 09/10/2020 Learning Krukshal

 Krukshal Algorithm

It is an algorithm to find the minimum spanning tree of a graph. A tree that includes all the nodes and n-1 edges with minimum overall weight.
The way I applied Krukshal's algorithm at start was that I sorted every edge and picked them one by one. If I got an edge where both of the vertices were already added I would discard it. If I got an edge where only one was added then I would add the edge and count the other vertex. If I encountered with an edge where none of the vertices were added I would count both of them and do it until I got all the vertices but it had a flaw. I wasn't concerned if these edges were connected to each other in any way.
let's say I could get a graph with nodes connected in pairs and not connected to each other.

Now I learned Krukshal using geeks for geeks. Two most important functions that fixed my flaw are explained with the code.


Source(https://www.geeksforgeeks.org/kruskals-minimum-spanning-tree-using-stl-in-c/)

// C++ program for Kruskal's algorithm to find Minimum 
// Spanning Tree of a given connected, undirected and 
// weighted graph 
#include<bits/stdc++.h> 
using namespace std; 

// Creating shortcut for an integer pair 
typedef pair<int, int> iPair; 

// Structure to represent a graph 
struct Graph 
{ 
int V, E; 
vector< pair<int, iPair> > edges; 

// Constructor 
Graph(int V, int E) 
{ 
this->V = V; 
this->E = E; 
} 

// Utility function to add an edge 
void addEdge(int u, int v, int w) 
{ 
edges.push_back({w, {u, v}}); 
} 

// Function to find MST using Kruskal's 
// MST algorithm 
int kruskalMST(); 
}; 

// To represent Disjoint Sets 
struct DisjointSets 
{ 
int *parent, *rnk; 
int n; 

// Constructor. 
DisjointSets(int n) 
{ 
// Allocate memory 
this->n = n; 
parent = new int[n+1]; 
rnk = new int[n+1]; 

// Initially, all vertices are in 
// different sets and have rank 0. 
for (int i = 0; i <= n; i++) 
{ 
rnk[i] = 0; 

//every element is parent of itself 
parent[i] = i; 
} 
} 

// Find the parent of a node 'u' 
// Path Compression 
        // working of find function


int find(int u) 
{ 
/* Make the parent of the nodes in the path 
from u--> parent[u] point to parent[u] */
if (u != parent[u]) 
parent[u] = find(parent[u]); 
return parent[u]; 
} 

// Union by rank 
        // working of merge function
        

void merge(int x, int y) 
{ 
x = find(x), y = find(y); 

/* Make tree with smaller height 
a subtree of the other tree */
if (rnk[x] > rnk[y]) 
parent[y] = x; 
else // If rnk[x] <= rnk[y] 
parent[x] = y; 

if (rnk[x] == rnk[y]) 
rnk[y]++; 
} 
}; 

/* Functions returns weight of the MST*/

int Graph::kruskalMST() 
{ 
int mst_wt = 0; // Initialize result 

// Sort edges in increasing order on basis of cost 
sort(edges.begin(), edges.end()); 

// Create disjoint sets 
DisjointSets ds(V); 

// Iterate through all sorted edges 
vector< pair<int, iPair> >::iterator it; 
for (it=edges.begin(); it!=edges.end(); it++) 
{ 
int u = it->second.first; 
int v = it->second.second; 

int set_u = ds.find(u); 
int set_v = ds.find(v); 

// Check if the selected edge is creating 
// a cycle or not (Cycle is created if u 
// and v belong to same set) 
if (set_u != set_v) 
{ 
// Current edge will be in the MST 
// so print it 
cout << u << " - " << v << endl; 

// Update MST weight 
mst_wt += it->first; 

// Merge two sets 
ds.merge(set_u, set_v); 
} 
} 

return mst_wt; 
} 

// Driver program to test above functions 
int main() 
{ 
/* Let us create above shown weighted 
and unidrected graph */
int V = 9, E = 14; 
Graph g(V, E); 

// making above shown graph 
g.addEdge(0, 1, 4); 
g.addEdge(0, 7, 8); 
g.addEdge(1, 2, 8); 
g.addEdge(1, 7, 11); 
g.addEdge(2, 3, 7); 
g.addEdge(2, 8, 2); 
g.addEdge(2, 5, 4); 
g.addEdge(3, 4, 9); 
g.addEdge(3, 5, 14); 
g.addEdge(4, 5, 10); 
g.addEdge(5, 6, 2); 
g.addEdge(6, 7, 1); 
g.addEdge(6, 8, 6); 
g.addEdge(7, 8, 7); 

cout << "Edges of MST are \n"; 
int mst_wt = g.kruskalMST(); 

cout << "\nWeight of MST is " << mst_wt; 

return 0; 
} 

Comments

Post a Comment

Popular posts from this blog

LeetCode 3Sum

Question Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0. Notice that the solution set must not contain duplicate triplets. Brute force We can run 3 loops to check each possible triplets, we also need to eliminate the duplicates from both sides. this method will work but will work but will give time limit exceed after time constraints. To do this in given time limit we need to sort the array first and Create a loop that fixes the left most integer. This reduces the problem to 2sum for remaining array. For each loop iteration where duplicates are skipped, we need to do a left/right iteration using while loop. my code:
Read more

New start Day 2 (1/10/2020) codeforces 492B Vanya and Lantern

 question: (source: https://codeforces.com/problemset/problem/492/B)      Vanya And Lantern Vanya walks late at night along a straight street of length  l , lit by  n  lanterns. Consider the coordinate system with the beginning of the street corresponding to point  0 , and its end corresponding to the point  l . Then the  i -th lantern is at the point  a i . The lantern lights all points of the street that are at the distance of at most  d  from it, where  d  is some positive number, common for all lanterns. Vanya wonders: what is the minimum light radius  d  should the lanterns have to light the whole street? Input The first line contains two integers  n ,  l  ( 1 ≤  n  ≤ 1000 ,  1 ≤  l  ≤ 10 9 ) — the number of lanterns and the length of the street respectively. The next line contains  n  integers  a i  ( 0 ≤  a i  ≤  l ). Multiple lanterns can be loca...
Read more

Heap (min)

 Heap Heap is a data structure used to store numbers in form of binary tree i.e each node has two children. Heap is the data structure behind PriorityQueue. Insert and pop operation inside a heap is oh log(n) complexity and can be used in multiple insert and pop operation questions. It is efficient and used in fastest sorting as well as sorting only takes nlog(n) complexity at worst case. Important Functions for heap: 1.  Heapify: This function is a top down approach to set an given array into heap. The idea is to set the top priority Item at the parent node of given subtree of 3. We will compare priority of left item from parent and then from right item to that of winner of parent and left and then swap the top priority with parent item. If top priority wasn't the parent item then we call the heapify again for the right or left node with which the value was swapped. If we have a given array then we can run a loop into that array from bottom of tree to top (excluding leafs),i....
Read more