DEV Community

Jayaprasanna Roddam
Jayaprasanna Roddam

Posted on • Edited on

DSA: Graph - questions

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
 

Sentry image

Hands-on debugging session: instrument, monitor, and fix

Join Lazar for a hands-on session where you’ll build it, break it, debug it, and fix it. You’ll set up Sentry, track errors, use Session Replay and Tracing, and leverage some good ol’ AI to find and fix issues fast.

RSVP here →

Top comments (0)

Billboard image

The Next Generation Developer Platform

Coherence is the first Platform-as-a-Service you can control. Unlike "black-box" platforms that are opinionated about the infra you can deploy, Coherence is powered by CNC, the open-source IaC framework, which offers limitless customization.

Learn more

👋 Kindness is contagious

Please leave a ❤️ or a friendly comment on this post if you found it helpful!

Okay