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.

    Graphs Interview Questions

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 GraphsBeginner
  2. Graph Implementation – C, C++, C++ STL, Java Collections, PythonBeginner
  3. Depth First Search (DFS)Medium
  4. Arrival and departure time of vertices in DFSEasy
  5. Types of edges involved in DFS and relation between themBeginner
  6. Determine whether a graph is Bipartite using DFSMedium
  7. Topological Sort Algorithm for DAGMedium
  8. Kahn’s Topological Sort AlgorithmMedium
  9. Transitive closure of a graphEasy
  10. Determine whether an undirected graph is a tree (Acyclic Connected Graph)Medium
  11. 2–Edge Connectivity in a graphHard
  12. 2–Vertex Connectivity in a graphHard
  13. Check if a digraph is a DAG (Directed Acyclic Graph) or notMedium
  14. Disjoint–Set Data Structure (Union–Find Algorithm)Medium
  15. Check if a graph is strongly connected or notEasy
  16. Check if a graph is strongly connected or not using one DFS TraversalHard
  17. Union–Find Algorithm for cycle detection in a graphMedium
  18. Single-Source Shortest Paths – Bellman–Ford AlgorithmMedium
  19. All-Pairs Shortest Paths – Floyd Warshall AlgorithmEasy
  20. Find the cost of the shortest path in DAG using one pass of Bellman–FordMedium
  21. Determine a negative-weight cycle in a graphMedium
  22. Find all Possible Topological Orderings of a DAGHard
  23. Find correct order of alphabets in a given dictionary of ancient originHard
  24. Find the longest path in a Directed Acyclic Graph (DAG)Hard
  25. Print all k–colorable configurations of a graph (Vertex coloring of a graph)Medium
  26. Print all Hamiltonian paths present in a graphHard
  27. Graph Coloring ProblemMedium
  28. Kruskal’s Algorithm for finding Minimum Spanning TreeHard
  29. Eulerian cycle in directed graphsHard
  30. Find root vertex of a graphMedium
  31. Check whether an undirected graph is EulerianMedium
  32. Check if a set of words can be rearranged to form a circleHard
  33. Find itinerary from the given list of departure and arrival airportsEasy
  34. Single-Source Shortest Paths – Dijkstra’s AlgorithmMedium
  35. Chess Knight Problem | Find the shortest path from source to destinationHard
  36. Snake and Ladder ProblemHard
  37. Breadth-First Search (BFS)Medium
  38. Check if an undirected graph contains a cycle or notMedium
  39. Find maximum cost path in a graph from a given source to a given destinationMedium
  40. Total paths in a digraph from a given source to a destination having exactly m edgesMedium
  41. Least cost path in a digraph from a given source to a destination having exactly m edgesMedium
  42. Depth-First Search (DFS) vs Breadth-First Search (BFS)Beginner
  43. Bipartite GraphMedium
  44. Compute the least cost path in a weighted digraph using BFSMedium
  45. Find the path between given vertices in a directed graphEasy
  46. Construct a directed graph from an undirected graph that satisfies given constraintsMedium