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
Top comments (1)
Great list of graph theory problems! I was wondering, which of these algorithms would you say is most critical to master for coding interviews?