The Heap Space

  What is Minimum Spanning Tree (MST)? A Minimum Spanning Tree (MST) is a subset of the edges of a connected, undirected and weighted graph. Thus MST is a tree . MST connects all the vertices/nodes of the graph together.  MST does not contain any cycles . MST finds minimum edge weight . MST contains ( V-1) edges , where V is the number of vertices/nodes in the graph.  No. of Spanning Trees possible for a graph (caution: Here I am not talking about Minimum Spanning Tree, but Spanning Tree in general): [ |E|C|V-1| ] - [no. of cycles]       ( here C is Combination of pnc)  Kruskal's Algorithm uses a Disjoint Set Data Structure to find Minimum Spanning Tree. Kruskal's Algorithm is a greedy algorithm.   Kruskal's Algorithm 1. for each node perform makeSet() operation of disjoint set 2. sort each edge of the graph in non-decreasing order by weight  3. for each edge (u,v):          4. if findSet(u) != findSet(v)...

  In this implementation of the disjoint set using a tree, every node will have the following structure                    class Node{                              int rank;                              int data;                              Node parent;                    } Each node will contain a single element and will represent a disjoint set containing that single element. Union by rank  always attaches the shorter tree to the root of the taller tree. Thus, the resulting tree is no taller than the originals unless they were of equal height, in which case the resulting tree is taller by one node. Time Complexity...

  What is a Disjoint Set? Well, Wikipedia has the perfect definition -  A disjoint-set data structure (also called a union-find data structure or merge–find set) is a data structure that tracks a set of elements partitioned into a number of disjoint (non-overlapping) subsets. It provides near-constant-time operations to add new sets, to merge existing sets, and to determine whether elements are in the same set. In addition to many other uses, disjoint-sets play a key role in Kruskal's algorithm for finding the minimum spanning tree of a graph. The disjoint set has mainly 3 Operations: makeset() -> makes 'n' number of disjoint sets containing single elements find(currentSet) -> returns the representative/parent of currentSet union(set1,set2) -> merges two disjoint sets represented by set1 and set2 into a new disjoint set.  Before going through code, I would recommend watching this video -  https://www.youtube.com/watch?v=wU6udHRIkcc Code: public class Mai...

  Single Source Shortest Path Algorithms BFS Dijkstra's Algorithm Bellman Ford Algorithm Time Complexity O(V^2) O(V^2) O(E.V) Space Complexity O(E) O(V) O(V) Limitation Does not work for weighted graphs in general. If all weight is same in weighted graph or can be made same, then it will work for weighted graph as well Works for weighted as well as unweighted graph. Does not work is there is a negative cycle in the graph. Not able to detect negative cycle. No limitation for working. Works for all kinds of graph as well as able to detect negative cycle in the graph. Only disadvantage is it's runtime complexity is highest here as compared to BFS, Dijkstra and Floyd Warshall Working for Unweighted Graph use this as it is easy to implement Avoid it as we have to implement a min heap too in this case which will slow this down Avoid it as Time Complexity is not good Working for Weighted Graph (no negative cycle) Not supported can be used Avoid it as Time Complexity is not good Workin...

    What is All Pairs Shortest Path (APSP)?  It calculates the shortest distance between each pair of vertices/nodes of the graph. We can also implement APSP by BFS, Dijkstra's Algorithm and Bellman-Ford Algorithm by running these algorithms for all the vertices/nodes in the graph/ Here we will be discussing a new algorithm for calculating only All Pairs Shortest Path. That means it can't be used to find the Single Source Shortest Path. The name of the algorithm is the  Floyd Warshall Algorithm.  The Floyd Warshall Algorithm does not work for / detects a negative cycle. Floyd Warshall Algorithm [Time Complexity: O(V^3) ,  Space Complexity: O(V^2) ] 1. Initialize a square matrix (adjacency matrix):          a. If i==j , put 0 in that cell          b. Else if there is a direct edge from node i to node j then we put the weight of that edge in that cell.          c. Else if there is no ...

    Why to use Bellman Ford Algorithm? We have seen earlier that both BFS and Dijkstra's algorithm can not be used when we have negative cycle in a graph. So, Bellman Ford Algorithm gives us a way to handle negative cycle in a graph. Remember, in any graph, if we have a negative cycle, we can't use any algorithm to find shortest path. Bellman Ford algorithm helps us to detect and notify the negative cycle in a graph, if present any.  In Bellman Ford Algorithm, our focus is gonna be on edges rather than vertices or nodes. To recall, in Dijkstra's Algorithm, our focus was on nodes. The Bellman Ford Algorithm runs for (V-1) times where V is the no. of vertices/nodes in the graph.In each iteration it go es through all edges and tries to find the optimal shortest distance. Why it runs (V-1) times, we will see to it later in this post. If there is a negative cycle present in graph, the Bellman Ford algorithm can detect it in Vth (V is the no. of vertices/nodes in the grap...

  Why do we need Dijkstra's Algorithm? We have seen that BFS can only be used to find the shortest path in unweighted graphs. So, for the weighted graphs, Dijkstra comes to our rescue. Dijkstra can be used for all 6 types of graphs. BUT, there is a scenario where DIJKSTRA's ALGORITHM CAN NOT BE USED : when a graph has a NEGATIVE CYCLE .  So a path is called a 'Negative Cycle' if: a) There is a cycle (quite obvious, isn't it ?) b) The Total weight of the cycle should be a negative number. For example - for now, let's consider in the above graph, the weight of edge AD as -6 instead of +6. Now, if we see the path DBAD, it is a cycle and total weight = 1 + 3 - 6 = -2, that is negative weight. So, a negative cycle. So, what is the reason that Dijkstra's Algorithm fails for a negative cycle? For one more time let's consider in the above graph the weight of edge AD as -6 instead of +6.  Now, we know Dijkstra finds the shortest path. If the graph has a negative...