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
Top comments (0)