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) }**

In this post, we have list out commonly asked interview questions that uses graph data structure –

- Terminology and Representations of Graphs

- Graph Implementation using STL

- Graph Implementation in C++ without using STL

- Graph Implementation in C

- Graph Implementation in Java using Collections

- Breadth First Search (BFS) | Iterative & Recursive Implementation

- Depth First Search (DFS) | Iterative & Recursive Implementation

- Arrival and Departure Time of Vertices in DFS

- Types of edges involved in DFS and relation between them

- Bipartite Graph

- Determine if a given graph is Bipartite Graph using DFS

- Minimum number of throws required to win Snake and Ladder game

- Topological Sorting in a DAG

- Kahn’s Topological Sort Algorithm

- Transitive Closure of a Graph

- Check if an undirected graph contains cycle or not

- Total paths in given digraph from given source to destination having exactly m edges

- Determine if an undirected graph is a Tree (Acyclic Connected Graph)

- 2-Edge Connectivity in the graph

- 2-Vertex Connectivity in the graph

- Check if given digraph is a DAG (Directed Acyclic Graph) or not

- Disjoint-Set Data Structure (Union-Find Algorithm)

- Chess Knight Problem – Find Shortest path from source to destination

- Check if given Graph is Strongly Connected or not

- Check if given Graph is Strongly Connected or not using one DFS Traversal

- Union-Find Algorithm for Cycle Detection in undirected graph

- Kruskal’s Algorithm for finding Minimum Spanning Tree

- Single-Source Shortest Paths – Dijkstra’s Algorithm

- Single-Source Shortest Paths – Bellman Ford Algorithm

- All-Pairs Shortest Paths – Floyd Warshall Algorithm

- Find Cost of Shortest Path in DAG using one pass of Bellman-Ford

- Least Cost Path in Weighted Digraph using BFS

- Find maximum cost path in graph from given source to destination

- Determine negative-weight cycle in a graph

- Least cost path in given digraph from given source to destination having exactly m edges

- Print all k-colorable configurations of the graph (Vertex coloring of graph)

- Print All Hamiltonian Path present in a graph

- Greedy coloring of graph

**Thank you for being with us. 🙂**

## Leave a Reply

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

This is awesome man! thanks a lot..

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

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.