Sign in

Graph Algo’s

Dijkstra’s shortest path algorithm

Relaxation Rule :

Approach :

Whenever distance of a vertex is reduced, we add one more instance of vertex in priority_queue. Even if there are multiple instances, we only consider the instance with minimum distance and ignore other instances since minHeap stores the min at the top

The time complexity remains O(ELogV)) as there will be at most O(E) vertices in priority queue and O(Log E) is same as O(Log V)

Code ( O(NlogN) time & O(N) space ) :

source code github

Notes:
1) The code calculates shortest distance, but doesn’t calculate the path information. We can create a parent array, update the parent array when distance is updated and use it show the shortest path from source to different vertices.
2) The code is for undirected graph, same dijkstra function can be used for directed graphs also.
3) The code finds shortest distances from source to all vertices. If we are interested only in shortest distance from the source to a single target, we can break the for the loop when the picked minimum distance vertex is equal to target (Step 3.a of the algorithm).
4) Time Complexity of the implementation is O(V²) if matrix is used & If the input graph is represented using adjacency list, it can be reduced to O(E log V) with the help of binary heap. (which I did xD )
5) Dijkstra’s algorithm doesn’t work for graphs with negative weight cycles, it may give correct results for a graph with negative edges. For graphs with negative weight edges and cycles, Bellman–Ford algorithm can be used, we will soon be discussing it as a separate post.

See here & try to apply Dijkstra ‘s algo here…we already visited node 2 with dist as 3 but due to negtative weights , now the new dist of node 2 is -3 which should be the ans but since we already visited the node we cannot again visit the nodes due to dijkstra

Spanning Tree

Given a connected and undirected graph, a spanning tree of that graph is a subgraph that is a tree and connects all the vertices together. A single graph can have many different spanning trees.

If a graph is a complete graph with n vertices, then total number of spanning trees is n^(n-2)

No of spanning trees in general

Min Spanning Tree (MST)

  • A minimum spanning tree (MST) or minimum weight spanning tree for a weighted, connected, undirected graph is a spanning tree with a weight less than or equal to the weight of every other spanning tree.
  • The weight of a spanning tree is the sum of weights given to each edge of the spanning tree.

How many edges does a minimum spanning tree has?
A minimum spanning tree has (V — 1) edges where V is the number of vertices in the given graph.

Note: For non connected graph we cannot form spanning trees

Prim’s Algo for Min Spanning Tree (MST)| Greedy

We start from any one vertex and keep adding edges with the lowest weight until we reach our goal.

The steps for implementing Prim’s algorithm are as follows:

  1. Initialize the minimum spanning tree with any vertex (usually the 1st)
  2. Find all the adjacent edges to the selected vertex and select the edge with the min weight (incase of multiple same min, select any one)
  3. Keep repeating step 2 until we get a minimum spanning tree
  4. Make sure while selecting the min edge that it always connects a new vertex else a cycle will be formed which we dont want(so in a way we select the next min)
Cycle should not be formed in any case

Approach for C++ implementation

3 arrays : key[ ] for choosing the next vertex with min weight, mstSet[ ] for to to represent the vertices present in MST, parent[ ] for printing the MST

Initially choose min value vertex i.e. zero and update its key as zero so that it is chosen first and now take a loop for V-1 times and in each iteration we’ll get a vertex which will be min value in the key [ ] , mark is as included in MST and then we consider its adjacent vertices & update their parent & key only with its weight and would not mark them as included because that we would do in next iteration for them i.e in each iteration we only mark 1 vertex with the min key and for its adjacent vertives we just update their parent with that marked vertex & key with their weight of the edge

Code (using matrix)

Time Complexity of the above program is O(V²).

Note: The following code snippet has time complexity of O(N+E) not O(N²)

So the above code has time comp = 0(V+E)*N=O(V²)

O(N+E)*O(N)= O(N²)

Optimal Approach

Instead of traversing the whole key[ ] to find the min we can use min heap so that O(N) becomes O(logN)

Code :

Time Complexity Analysis

  • If adjacency list is used to represent the graph, then using breadth first search, all the vertices can be traversed in O(V + E) time.
  • We traverse all the vertices of graph using breadth first search and use a min heap for storing the vertices not yet included in the MST.
  • To get the minimum weight edge, we use min heap as a priority queue.
  • Min heap operations like extracting minimum element takes O(logV) time.

So, overall time complexity

= O(E + V) x O(logV)

= O((E + V)logV)

= O(ElogV)

How Printing takes place ?

Suppose that’s how a MST was formed step by step then printing will be as follow : (see the pic)

Question: The task is to find the sum of weights of the edges of the Minimum Spanning Tree.(here check my solution) or hackerearth sexy solution

Disjoint Set

Must see resources :

GFG Disjoint Set , DSU detect cycle set 1, DSU detect cycle set 2

Now we are ready to do Kruskal’s Algo

Approach:

We start from the edges with the lowest weight and keep adding edges until we reach our goal.

The steps for implementing Kruskal’s algorithm are as follows:

  • Sort all the edges from low weight to high
  • Take the edge with the lowest weight and add it to the spanning tree. If adding the edge created a cycle, then reject this edge.
  • Keep adding edges until we reach all vertices.

Note: we dont take any adjacent list here because we need to store edges only (not to traverse the graph ) and to sort edges in ascending order according to their weights so use a structure instead

We’ll take vector<pair<int,int>> mst to store the edges of the MST

To detect a cycle , we’ll find parent of the 2 components if they are same then a cycle exists

Code : ( O(E logV time ) )

Another implementation (hackerearth)

a student at heart