Graphs Interview Questions

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 above graph,

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

Below is the list of commonly asked graphs interview questions –


  1. Graph Implementation using STL
  2. Graph Implementation in C++ without using STL
  3. Breadth First Search (BFS) | Iterative & Recursive Implementation
  4. Depth First Search (DFS) | Iterative & Recursive Implementation
  5. Arrival and Departure Time of Vertices in DFS
  6. Types of edges involved in DFS and relation between them
  7. Bipartite Graph
  8. Minimum number of throws required to win Snake and Ladder game
  9. Topological Sorting in a DAG
  10. Transitive Closure of a Graph
  11. Check if an undirected graph contains cycle or not
  12. Total paths in given digraph from given source to destination having exactly m edges
  13. Determine if an undirected graph is a Tree (Acyclic Connected Graph)
  14. 2-Edge Connectivity in the graph
  15. 2-Vertex Connectivity in the graph
  16. Check if given digraph is a DAG (Directed Acyclic Graph) or not
  17. Disjoint-Set Data Structure (Union-Find Algorithm)
  18. Chess Knight Problem – Find Shortest path from source to destination
  19. Check if given Graph is Strongly Connected or not
  20. Check if given Graph is Strongly Connected or not using one DFS Traversal
  21. Union-Find Algorithm for Cycle Detection in undirected graph
  22. Kruskal’s Algorithm for finding Minimum Spanning Tree
  23. Single-Source Shortest Paths – Dijkstra’s Algorithm
  24. Single-Source Shortest Paths – Bellman Ford Algorithm
  25. All-Pairs Shortest Paths – Floyd Warshall Algorithm
  26. Print all k-colorable configurations of the graph (Vertex coloring of graph)
  27. Print All Hamiltonian Path present in a graph
  28. Greedy coloring of graph


Thank you all for your valuable time and being with us. 🙂