DEV Community

Nozibul Islam
Nozibul Islam

Posted on

8 6 6 6 6

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

Image of Timescale

🚀 pgai Vectorizer: SQLAlchemy and LiteLLM Make Vector Search Simple

We built pgai Vectorizer to simplify embedding management for AI applications—without needing a separate database or complex infrastructure. Since launch, developers have created over 3,000 vectorizers on Timescale Cloud, with many more self-hosted.

Read more

Top comments (1)

Collapse
 
avanichols_dev 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?

Image of Docusign

🛠️ Bring your solution into Docusign. Reach over 1.6M customers.

Docusign is now extensible. Overcome challenges with disconnected products and inaccessible data by bringing your solutions into Docusign and publishing to 1.6M customers in the App Center.

Learn more