write an analysis/demonstration of the Big O time for the algorithm kruskal\'s a
ID: 3826046 • Letter: W
Question
write an analysis/demonstration of the Big O time for the algorithm
kruskal's algorithm
— can you please comment each line of code with the big o notation!
here is the attached code :
// Java program for Kruskal's algorithm to find Minimum Spanning Tree
// of a given connected, undirected and weighted graph
import java.util.*;
import java.lang.*;
import java.io.*;
class Graph
{
// A class to represent a graph edge
class Edge implements Comparable
{
int src, dest, weight;
// Comparator function used for sorting edges based on
// their weight
public int compareTo(Edge compareEdge)
{
return this.weight-compareEdge.weight;
}
};
// A class to represent a subset for union-find
class subset
{
int parent, rank;
};
int V, E; // V-> no. of vertices & E->no.of edges
Edge edge[]; // collection of all edges
// Creates a graph with V vertices and E edges
Graph(int v, int e)
{
V = v;
E = e;
edge = new Edge[E];
for (int i=0; i
edge[i] = new Edge();
}
// A utility function to find set of an element i
// (uses path compression technique)
int find(subset subsets[], int i)
{
// find root and make root as parent of i (path compression)
if (subsets[i].parent != i)
subsets[i].parent = find(subsets, subsets[i].parent);
return subsets[i].parent;
}
// A function that does union of two sets of x and y
// (uses union by rank)
void Union(subset subsets[], int x, int y)
{
int xroot = find(subsets, x);
int yroot = find(subsets, y);
// Attach smaller rank tree under root of high rank tree
// (Union by Rank)
if (subsets[xroot].rank < subsets[yroot].rank)
subsets[xroot].parent = yroot;
else if (subsets[xroot].rank > subsets[yroot].rank)
subsets[yroot].parent = xroot;
// If ranks are same, then make one as root and increment
// its rank by one
else
{
subsets[yroot].parent = xroot;
subsets[xroot].rank++;
}
}
// The main function to construct MST using Kruskal's algorithm
void KruskalMST()
{
Edge result[] = new Edge[V]; // Tnis will store the resultant MST
int e = 0; // An index variable, used for result[]
int i = 0; // An index variable, used for sorted edges
for (i=0; i
result[i] = new Edge();
// Step 1: Sort all the edges in non-decreasing order of their
// weight. If we are not allowed to change the given graph, we
// can create a copy of array of edges
Arrays.sort(edge);
// Allocate memory for creating V ssubsets
subset subsets[] = new subset[V];
for(i=0; i
subsets[i]=new subset();
// Create V subsets with single elements
for (int v = 0; v < V; ++v)
{
subsets[v].parent = v;
subsets[v].rank = 0;
}
i = 0; // Index used to pick next edge
// Number of edges to be taken is equal to V-1
while (e < V - 1)
{
// Step 2: Pick the smallest edge. And increment the index
// for next iteration
Edge next_edge = new Edge();
next_edge = edge[i++];
int x = find(subsets, next_edge.src);
int y = find(subsets, next_edge.dest);
// If including this edge does't cause cycle, include it
// in result and increment the index of result for next edge
if (x != y)
{
result[e++] = next_edge;
Union(subsets, x, y);
}
// Else discard the next_edge
}
// print the contents of result[] to display the built MST
System.out.println("Following are the edges in the constructed MST");
for (i = 0; i < e; ++i)
System.out.println(result[i].src+" -- "+result[i].dest+" == "+
result[i].weight);
}
// Java program for Kruskal's algorithm to find Minimum Spanning Tree
// of a given connected, undirected and weighted graph
import java.util.*;
import java.lang.*;
import java.io.*;
class Graph
{
// A class to represent a graph edge
class Edge implements Comparable
{
int src, dest, weight;
// Comparator function used for sorting edges based on
// their weight
public int compareTo(Edge compareEdge)
{
return this.weight-compareEdge.weight;
}
};
// A class to represent a subset for union-find
class subset
{
int parent, rank;
};
int V, E; // V-> no. of vertices & E->no.of edges
Edge edge[]; // collection of all edges
// Creates a graph with V vertices and E edges
Graph(int v, int e)
{
V = v;
E = e;
edge = new Edge[E];
for (int i=0; i
edge[i] = new Edge();
}
// A utility function to find set of an element i
// (uses path compression technique)
int find(subset subsets[], int i)
{
// find root and make root as parent of i (path compression)
if (subsets[i].parent != i)
subsets[i].parent = find(subsets, subsets[i].parent);
return subsets[i].parent;
}
// A function that does union of two sets of x and y
// (uses union by rank)
void Union(subset subsets[], int x, int y)
{
int xroot = find(subsets, x);
int yroot = find(subsets, y);
// Attach smaller rank tree under root of high rank tree
// (Union by Rank)
if (subsets[xroot].rank < subsets[yroot].rank)
subsets[xroot].parent = yroot;
else if (subsets[xroot].rank > subsets[yroot].rank)
subsets[yroot].parent = xroot;
// If ranks are same, then make one as root and increment
// its rank by one
else
{
subsets[yroot].parent = xroot;
subsets[xroot].rank++;
}
}
// The main function to construct MST using Kruskal's algorithm
void KruskalMST()
{
Edge result[] = new Edge[V]; // Tnis will store the resultant MST
int e = 0; // An index variable, used for result[]
int i = 0; // An index variable, used for sorted edges
for (i=0; i
result[i] = new Edge();
// Step 1: Sort all the edges in non-decreasing order of their
// weight. If we are not allowed to change the given graph, we
// can create a copy of array of edges
Arrays.sort(edge);
// Allocate memory for creating V ssubsets
subset subsets[] = new subset[V];
for(i=0; i
subsets[i]=new subset();
// Create V subsets with single elements
for (int v = 0; v < V; ++v)
{
subsets[v].parent = v;
subsets[v].rank = 0;
}
i = 0; // Index used to pick next edge
// Number of edges to be taken is equal to V-1
while (e < V - 1)
{
// Step 2: Pick the smallest edge. And increment the index
// for next iteration
Edge next_edge = new Edge();
next_edge = edge[i++];
int x = find(subsets, next_edge.src);
int y = find(subsets, next_edge.dest);
// If including this edge does't cause cycle, include it
// in result and increment the index of result for next edge
if (x != y)
{
result[e++] = next_edge;
Union(subsets, x, y);
}
// Else discard the next_edge
}
// print the contents of result[] to display the built MST
System.out.println("Following are the edges in the constructed MST");
for (i = 0; i < e; ++i)
System.out.println(result[i].src+" -- "+result[i].dest+" == "+
result[i].weight);
}
Explanation / Answer
Code:
//Java program for Kruskal's algorithm to find Minimum Spanning Tree
//of a given connected, undirected and weighted graph
import java.util.*;
import java.lang.*;
import java.io.*;
class Graph
{
// A class to represent a graph edge
class Edge implements Comparable // O(1)
{
int src, dest, weight; // O(1)
// Comparator function used for sorting edges based on
// their weight
public int compareTo(Edge compareEdge)
{
return this.weight-compareEdge.weight; // O(1)
}
};
// A class to represent a subset for union-find
class subset // O(1)
{
int parent, rank; // O(1)
};
int V, E; // V-> no. of vertices & E->no.of edges // O(1)
Edge edge[]; // collection of all edges // O(1)
// Creates a graph with V vertices and E edges
Graph(int v, int e) // // O(E)
{
V = v;
E = e;
edge = new Edge[E];
for (int i=0; i<E;i++) // O(E)
edge[i] = new Edge(); // O(1)
}
// A utility function to find set of an element i
// (uses path compression technique)
int find(subset subsets[], int i) // O(log V)
{
// find root and make root as parent of i (path compression)
if (subsets[i].parent != i) // O(1)
subsets[i].parent = find(subsets, subsets[i].parent);
return subsets[i].parent; // O(1)
}
// A function that does union of two sets of x and y
// (uses union by rank)
void Union(subset subsets[], int x, int y) // O(log V)
{
int xroot = find(subsets, x); //O(log V)
int yroot = find(subsets, y); //O(log V)
// Attach smaller rank tree under root of high rank tree
// (Union by Rank)
if (subsets[xroot].rank < subsets[yroot].rank) //O(1)
subsets[xroot].parent = yroot; //O(1)
else if (subsets[xroot].rank > subsets[yroot].rank) //O(1)
subsets[yroot].parent = xroot; //O(1)
// If ranks are same, then make one as root and increment
// its rank by one
else
{
subsets[yroot].parent = xroot; //O(1)
subsets[xroot].rank++; //O(1)
}
}
// The main function to construct MST using Kruskal's algorithm
void KruskalMST()
{
Edge result[] = new Edge[V]; // Tnis will store the resultant MST //O(1)
int e = 0; // An index variable, used for result[] //O(1)
int i = 0; // An index variable, used for sorted edges //O(1)
for (i=0; i<V;i++) //O(V)
result[i] = new Edge(); //O(1)
// Step 1: Sort all the edges in non-decreasing order of their
// weight. If we are not allowed to change the given graph, we
// can create a copy of array of edges
Arrays.sort(edge); //O(E log E)
// Allocate memory for creating V ssubsets
subset subsets[] = new subset[V]; //O(1)
for(i=0; i<v;i++) //O(V)
subsets[i]=new subset(); //O(1)
// Create V subsets with single elements
for (int v = 0; v < V; ++v) //O(V)
{
subsets[v].parent = v; //O(1)
subsets[v].rank = 0; //O(1)
}
i = 0; // Index used to pick next edge //O(1)
// Number of edges to be taken is equal to V-1
while (e < V - 1) // O(E)
{
// Step 2: Pick the smallest edge. And increment the index
// for next iteration
Edge next_edge = new Edge(); //O(1)
next_edge = edge[i++]; //O(1)
int x = find(subsets, next_edge.src); // O(log V)
int y = find(subsets, next_edge.dest); // O(log V)
// If including this edge does't cause cycle, include it
// in result and increment the index of result for next edge
if (x != y) //O(1)
{
result[e++] = next_edge; //O(1)
Union(subsets, x, y); //O(log V)
}
// Else discard the next_edge
}
// print the contents of result[] to display the built MST
System.out.println("Following are the edges in the constructed MST"); //O(1)
for (i = 0; i < e; ++i) //O(V)
System.out.println(result[i].src+" -- "+result[i].dest+" == "+ result[i].weight); //O(1)
}
}
Time complexity by function:
class subset // O(1)
Graph(int v, int e) // // O(E)
int find(subset subsets[], int i) // O(log V)
void Union(subset subsets[], int x, int y) // O(log V) { O( log v + log v + 1 + 1) = O(log v) }
time complexity of Kruskal:
T(kriskal) = O(1) + O(1) + O(1) + V * O(1) + O(E log E) + O(1) + O(1) + V * O(1) + V * O(1) +
O(E) * { O(1) + O(1) + O(log V) + O(log V) +O(log V) }
+ V * O(1)
= O(E log E) +O(E log V) since in a connected graph E>=(V-1)
= O(E log E)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.