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 –

- Graph Implementation using STL

- Graph Implementation in C++ without using STL

- 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

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

- Topological Sorting in a DAG

- 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

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

- Print All Hamiltonian Path present in a graph

- Greedy coloring of graph

- Determine if a given graph is Bipartite Graph using DFS

**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…

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.