Hi All,

I have created this post to share my notes on graph. I always faced problem in understanding graph problem and even if I understand the problem then next worry is which data strucutre and algorithm is used to solve this problem.

This post does not have any shortcut to remember templates or code. This post has important graph algorithms and resources to learn these algorithms.

After solving problem related to each topic, I am confident to implement the required algorithm quickly. These building blocks also help me to revise the concept of graph just before the interview.

Please upvote the posts so that it will reach max folks and everyone will get benefit out of it.

How to declare data structure for storing graph?

Unweighted Graph
List[] graph = new List[n];

Weighted Graph
List<int[]>[] graph = new List[n];

Tree vs Graph
Visited array is used in graph to avoid processing of the same node again.

Algorithm used to traverse/search in graph

BFS

1. Used for finding shortest path
2. Time Complexity is O(V+ E)

DFS

1. Used for finding if path exists/possible
2. Time Complexity is O(V+ E)

Check if cycle exist in graph

Directed
Use color array with value 0, 1 and 2

Undirected

1. Use union find
2. use parent pointer and visited array ( DFS or BFS)

Topological Sort (Directed Acyclic Graph)
https://www.interviewcake.com/concept/java/topological-sort

BFS

1. InDegree Array and start with indegree 0
2. Important to check for length of topo sort array with total number of vertices to detect cycle.
3. Time Complexity is O(V+ E).
4. It is easier to check cycles in BFS.

DFS

1. Add current node at start of list only after processing all child nodes.
2. No need for indegree nodes. Just do dfs until all nodes are visited
3. Time Complexity is O(V+ E)

Single Source Shortest Path

1. Topological Sort

1. Perform Topo Sort
2. Traverse graph in topo sort order. ie. Pick start vertex from top sort and explore its neighbours and keep maintaining shortest distance.
3. Time Complexity is O(V + E).

2. Dijkstra Algorithm

• Used only if weights are non-negative
• Similar to BFS but has below difference
• Used Priority Queue with Integer Array instead of Queue with Integer
• Used Distance array instead of boolean visited array.
• Time Complexity is O(Elog E) -> O(Elog V^2) -> O(E*2 log v) -> O(ElogV)
• https://leetcode.com/problems/network-delay-time
• https://leetcode.com/problems/cheapest-flights-within-k-stops/ - Imp as slight variation

Bellman Ford

• Used with negative weights also.
• Able to find whether graph has negative cycle
• Not preferred over Dijkstra as time complexity of bellman ford is O(VE)
• Implemented Bellman ford for this problem to see its working code. https://leetcode.com/problems/network-delay-time
• Run this algo one more time if a negative cycle check is required. If the shortest distance of a vertex is reduced, then the graph has a negative cycle.

All Pair Shortest Path Algorithm

Floyd Warshall Algorithm

• It prefers adjacency matrix over adjacency list
• Time Complexity is O(V^3)
• Run this algo one more time if a negative cycle check is required. If the shortest distance of a vertex is reduced, then the graph has a negative cycle.
• https://leetcode.com/problems/find-the-city-with-the-smallest-number-of-neighbors-at-a-threshold-distance/

Strongly Connected Components(SCC)

Simple DFS and visited array is used to find scc in an undirected graph.

Tarjan algo and kosaraju algo are used to find scc in directed graphs.

Tarjan’s Algorithm

• Used to find scc, articulation point, bridge in graph.
• Time complexity is O(V+E)
• - scc
• Implemented both bridge and articulation points in this leetcode problem
• https://leetcode.com/problems/critical-connections-in-a-network
• - Bridge and Articulation Point

Kosaraju’s Algorithm

• Time Complexity is O(V+E)
• Implemented on HackerEarth by me
• https://www.hackerearth.com/practice/algorithms/graphs/strongly-connected-components/practice-problems/algorithm/a-walk-to-remember-qualifier2/submissions/
• Implementation: https://leetcode.com/problems/course-schedule/discuss/249688/Different-O(V%2BE)-solution-using-Kosaraju's-algorithm

Minimum Spanning Tree

Prims Algo

• Start with any vertex. Use Priority Queue to process the smallest edge.
• Use visited array or distance array.
• Difference between Prims and Dijkstra is “Don’t add current vertex distance to calculate neighbour distance”.
• Example : u, v
• Dijkstra - dis[v] = dis[u] + graph[u][v];
• Prims - dis[v] = graph[u][v]
• Time Complexity is O(ElogV)
• Implementation: https://leetcode.com/problems/min-cost-to-connect-all-points

Kruskal Algo

• Sort all the edges by their weights and use union find to avoid cycle
• Time Complexity is O(ElogE)
• Implementation: https://leetcode.com/problems/min-cost-to-connect-all-points

Travelling Salesman Problem (TSP)

• It is a hamiltonian circuit. It is a hamiltonian path if returning to the start vertex is not needed.
• Time Complexity is O(N^2 * 2 ^N)
• Implemented using dp with bit masking as dp[1<<N][N] where N is number of vertices.
• Easiest Implementation: https://www.hackerearth.com/practice/notes/codemonk-dynamic-programming-ii-1/
• https://leetcode.com/problems/find-the-shortest-superstring

Hamiltonian Path or TSP

• Path which traverses each vertex exactly once.
• Simple way: DFS + backtracking
• https://www.hackerearth.com/practice/algorithms/graphs/hamiltonian-path/tutorial/

Euler Path

• Path which traverses each edge exactly once.
• Implementation: https://leetcode.com/problems/reconstruct-itinerary/

Graph beginner problems:
https://leetcode.com/discuss/general-discussion/655708/graph-for-beginners-problems-pattern-sample-solutions/

If I missed anything or written wrongly, please let me know. I will keep updating the post.
Next: I will be writing the same for Dynamic Programming.