Graph Data Structure: Interview Questions and Practice Problems

A graph is an ordered pair `G = (V, E)` comprising a set `V` of vertices or nodes, and a collection of pairs of vertices from `V` called edges of the graph.

For example, for the above graph,

V = { 1, 2, 3, 4, 5, 6 }
E = { (1, 4), (1, 6), (2, 6), (4, 5), (5, 6) }

In this post, we have listed out commonly asked interview questions that use graph data structure:

1. Terminology and Representations of Graphs
2. Graph Implementation — C, C++, C++ STL, Java Collections, Python
3. Depth First Search (DFS)
4. Arrival and departure time of vertices in DFS
5. Types of edges involved in DFS and relation between them
6. Determine whether a graph is Bipartite using DFS
7. Topological Sort Algorithm for DAG
8. Kahn’s Topological Sort Algorithm
9. Transitive closure of a graph
10. Determine whether an undirected graph is a tree (Acyclic Connected Graph)
11. 2–Edge Connectivity in a graph
12. 2–Vertex Connectivity in a graph
13. Check if a digraph is a DAG (Directed Acyclic Graph) or not
14. Disjoint–Set Data Structure (Union–Find Algorithm)
15. Check if a graph is strongly connected or not
16. Check if a graph is strongly connected or not using one DFS Traversal
17. Union–Find Algorithm for cycle detection in a graph
18. Single-Source Shortest Paths — Bellman–Ford Algorithm
19. All-Pairs Shortest Paths — Floyd Warshall Algorithm
20. Find the cost of the shortest path in DAG using one pass of Bellman–Ford
21. Determine a negative-weight cycle in a graph
22. Find all Possible Topological Orderings of a DAG
23. Find correct order of alphabets in a given dictionary of ancient origin
24. Find the longest path in a Directed Acyclic Graph (DAG)
25. Print all k–colorable configurations of a graph (Vertex coloring of a graph)
26. Print all Hamiltonian paths present in a graph
27. Graph Coloring Problem
28. Kruskal’s Algorithm for finding Minimum Spanning Tree
29. Eulerian cycle in directed graphs
30. Find root vertex of a graph
31. Check whether an undirected graph is Eulerian
32. Check if a set of words can be rearranged to form a circle
33. Find itinerary from the given list of departure and arrival airports
34. Single-Source Shortest Paths — Dijkstra’s Algorithm
35. Chess Knight Problem | Find the shortest path from source to destination
36. Snake and Ladder Problem
37. Breadth-First Search (BFS)
38. Check if an undirected graph contains a cycle or not
39. Find maximum cost path in a graph from a given source to a given destination
40. Total paths in a digraph from a given source to a destination having exactly `m` edges
41. Least cost path in a digraph from a given source to a destination having exactly `m` edges
42. Depth-First Search (DFS) vs Breadth-First Search (BFS)
43. Bipartite Graph
44. Compute the least cost path in a weighted digraph using BFS
45. Find the path between given vertices in a directed graph
46. Construct a directed graph from an undirected graph that satisfies given constraints