Graphs 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.

  Graphs Interview Questions

For example for 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 list out commonly asked interview questions that uses graph data structure –

 

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

 
 

Thank you for being with us. 🙂

 


Leave a Reply

avatar
  Subscribe  
newest oldest most voted
Notify of
throwaway2016
Guest

Thanks,, this is really interesting and I’ll probably read through all of them just to brush up on my graph knowledge…

Mike
Guest

This is awesome man! thanks a lot..

will
Guest

Very interesting stuff though. Love graph algorithms have coded many myself in JavaScript to prep for interviews. My algorithms code base test suite –
https://travis-ci.org/williscool/code_gym/jobs/129218676

mooneater
Guest

Much more applicable than knowing how to implement these techniques, would be knowledge of “how to solve given realworld problems with these concepts”. It is likely a developer would have access to optimized libraries implementing these, and would need to know when they apply.