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

Postmark Image

Speedy emails, satisfied customers

Are delayed transactional emails costing you user satisfaction? Postmark delivers your emails almost instantly, keeping your customers happy and connected.

Sign up

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?

Sentry image

See why 4M developers consider Sentry, “not bad.”

Fixing code doesn’t have to be the worst part of your day. Learn how Sentry can help.

Learn more

👋 Kindness is contagious

Engage with a sea of insights in this enlightening article, highly esteemed within the encouraging DEV Community. Programmers of every skill level are invited to participate and enrich our shared knowledge.

A simple "thank you" can uplift someone's spirits. Express your appreciation in the comments section!

On DEV, sharing knowledge smooths our journey and strengthens our community bonds. Found this useful? A brief thank you to the author can mean a lot.

Okay