DSA: Graph Theory Questions for Interviews and Practice

DSA: Graph Theory Questions for Interviews and Practice.

1. Graph Basics

• Representing Graphs Using Adjacency Matrix
• Representing Graphs Using Adjacency List
• Implementing a Graph Using an Edge List
• Implementing Depth-First Search (DFS)
• Implementing Breadth-First Search (BFS)
• Checking if a Graph is Connected (Undirected)
• Counting Connected Components in an Undirected Graph
• Checking if a Graph is Bipartite (DFS and BFS)
• Detecting Cycle in an Undirected Graph (DFS and BFS)
• Detecting Cycle in a Directed Graph (DFS and BFS)

2. Shortest Path Algorithms

• Dijkstra’s Algorithm
• Bellman-Ford Algorithm
• Floyd-Warshall Algorithm
• Shortest Path in a Grid (BFS)
• Shortest Path in a Weighted Graph (Using Priority Queue)
• 0-1 BFS for Shortest Path in a Binary Graph
• Shortest Path in a Directed Acyclic Graph (DAG)
• Shortest Path in a Grid with Obstacles
• Shortest Path with Exactly K Edges
• All Pairs Shortest Path (Floyd-Warshall)

3. Graph Traversal and Connected Components

• Connected Components in an Undirected Graph
• Connected Components in a Directed Graph (Kosaraju’s Algorithm)
• Strongly Connected Components (Tarjan’s Algorithm)
• Articulation Points (Cut Vertices) in a Graph
• Bridges in a Graph
• Biconnected Components
• Finding All Cycles in a Graph
• Counting Cycles of Length 3 in an Undirected Graph
• Counting Cycles of Length 4 in an Undirected Graph
• Eulerian Path and Circuit in an Undirected Graph

4. Topological Sorting and DAGs

• Topological Sorting Using DFS
• Topological Sorting Using Kahn’s Algorithm (BFS)
• Longest Path in a Directed Acyclic Graph (DAG)
• Finding All Topological Orderings of a DAG
• Critical Path Method (CPM)
• Detecting Cycle in a DAG
• Minimum Number of Vertices to Traverse All Nodes (DAG)
• Path with Maximum Probability in a Directed Graph
• Kahn’s Algorithm for Detecting Cycles in a Graph
• Converting a Directed Graph to a DAG (Removing Cycles)

5. Minimum Spanning Tree (MST) Algorithms

• Prim’s Algorithm
• Kruskal’s Algorithm
• Minimum Spanning Tree for a Graph with Negative Weights
• Finding Second Minimum Spanning Tree
• Checking Uniqueness of Minimum Spanning Tree
• Boruvka’s Algorithm for MST
• Finding the Maximum Spanning Tree
• Minimum Cost to Connect All Points (Using MST)
• Minimum Spanning Tree for Dense Graphs
• Minimum Spanning Tree in a Grid

6. Network Flow and Matching Problems

• Ford-Fulkerson Algorithm for Maximum Flow
• Edmonds-Karp Algorithm for Maximum Flow
• Dinic’s Algorithm for Maximum Flow
• Minimum Cut in a Graph (Max-Flow Min-Cut Theorem)
• Bipartite Matching Using Network Flow
• Maximum Bipartite Matching (Hungarian Algorithm)
• Minimum Vertex Cover in a Bipartite Graph
• Finding Disjoint Paths in a Graph
• Circulation Problem in a Network
• Job Assignment Problem (Hungarian Algorithm)

7. Graph Coloring Problems

• Graph Coloring Using Backtracking
• Minimum Colors Required to Color a Graph (Greedy)
• Chromatic Number of a Graph
• Coloring a Bipartite Graph
• M-Coloring Problem (Backtracking)
• Vertex Coloring in a Tree
• Edge Coloring of a Graph
• Planar Graph Coloring (Four-Color Theorem)
• Graph Coloring to Solve Sudoku
• Coloring Graphs to Solve Map Coloring Problem

8. Advanced Graph Algorithms

• Johnson’s Algorithm for All-Pairs Shortest Path
• A* Search Algorithm
• Bidirectional Search Algorithm
• Tarjan’s Algorithm for Bridge-Finding
• Floyd-Warshall with Path Reconstruction
• Travelling Salesman Problem (Using Bitmasking + DP)
• Minimum Hamiltonian Cycle (Using Bitmasking + DP)
• Finding Longest Simple Path in a Graph
• Graph Isomorphism Check
• Tree Decomposition of a Graph

9. Grid and Matrix-Based Graph Problems

• Number of Islands Problem (DFS/BFS)
• Counting Connected Components in a Grid
• Rat in a Maze Problem
• Minimum Steps to Reach the End of a Grid
• Knight’s Shortest Path in a Chessboard
• Finding the Shortest Bridge Between Two Islands
• Minimum Distance to Traverse All Points in a Grid
• Path with Maximum Gold in a Grid
• Count the Number of Enclaves in a Grid
• Path with Maximum Sum in a Grid

10. Miscellaneous Graph Problems

• Course Schedule Problem (Topological Sort)
• Alien Dictionary (Topological Sort in a Directed Graph)
• Reconstruct Itinerary from Given Tickets (Eulerian Path)
• Word Ladder Problem (BFS)
• Minimum Swaps to Sort an Array Using Graph
• Reconstructing a Binary Tree from Preorder and Inorder Traversals (Using Graph Concepts)
• Steiner Tree Problem
• Finding Safe States in a Graph
• Graph-Based Recommendation Systems
• Finding the Center of a Star Graph

🔗 Connect with me on LinkedIn:

I regularly share insights on JavaScript, Node.js, React, Next.js, software engineering, data structures, algorithms, and more. Let’s connect, learn, and grow together!

Follow me: Nozibul Islam