Graph Data Structure: Interview Questions and Practice Problems
Published in
3 min readJul 7, 2018
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:
- Terminology and Representations of Graphs
- Graph Implementation — C, C++, C++ STL, Java Collections, Python
- Depth First Search (DFS)
- Arrival and departure time of vertices in DFS
- Types of edges involved in DFS and relation between them
- Determine whether a graph is Bipartite using DFS
- Topological Sort Algorithm for DAG
- Kahn’s Topological Sort Algorithm
- Transitive closure of a graph
- Determine whether an undirected graph is a tree (Acyclic Connected Graph)
- 2–Edge Connectivity in a graph
- 2–Vertex Connectivity in a graph
- Check if a digraph is a DAG (Directed Acyclic Graph) or not
- Disjoint–Set Data Structure (Union–Find Algorithm)
- Check if a graph is strongly connected or not
- Check if a graph is strongly connected or not using one DFS Traversal
- Union–Find Algorithm for cycle detection in a graph
- Single-Source Shortest Paths — Bellman–Ford Algorithm
- All-Pairs Shortest Paths — Floyd Warshall Algorithm
- Find the cost of the shortest path in DAG using one pass of Bellman–Ford
- Determine a negative-weight cycle in a graph
- Find all Possible Topological Orderings of a DAG
- Find correct order of alphabets in a given dictionary of ancient origin
- Find the longest path in a Directed Acyclic Graph (DAG)
- Print all k–colorable configurations of a graph (Vertex coloring of a graph)
- Print all Hamiltonian paths present in a graph
- Graph Coloring Problem
- Kruskal’s Algorithm for finding Minimum Spanning Tree
- Eulerian cycle in directed graphs
- Find root vertex of a graph
- Check whether an undirected graph is Eulerian
- Check if a set of words can be rearranged to form a circle
- Find itinerary from the given list of departure and arrival airports
- Single-Source Shortest Paths — Dijkstra’s Algorithm
- Chess Knight Problem | Find the shortest path from source to destination
- Snake and Ladder Problem
- Breadth-First Search (BFS)
- Check if an undirected graph contains a cycle or not
- Find maximum cost path in a graph from a given source to a given destination
- Total paths in a digraph from a given source to a destination having exactly `m` edges
- Least cost path in a digraph from a given source to a destination having exactly `m` edges
- Depth-First Search (DFS) vs Breadth-First Search (BFS)
- Bipartite Graph
- Compute the least cost path in a weighted digraph using BFS
- Find the path between given vertices in a directed graph
- Construct a directed graph from an undirected graph that satisfies given constraints