DEV Community

Nozibul Islam
Nozibul Islam

Posted on

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

Top comments (1)

Collapse
 
avanichols profile image
Ava Nichols

Great list of graph theory problems! I was wondering, which of these algorithms would you say is most critical to master for coding interviews?