Graph Data Structure is a collection of nodes connected by edges. It's used to represent relationships between different entities.
If you are looking for topic-wise list of problems on different topics like DFS, BFS, Topological Sort, Shortest Path, etc., please refer to Graph Algorithms.
Basics of Graph:
Easy Problems
- Breadth First Traversal for a Graph
- Depth First Traversal for a Graph
- Shortest path in an unweighted graph
- 0-1 BFS (Shortest Path in a Binary Weight Graph)
- Count number of trees in a forest
- Topological Sorting
- All topological sorts of a Directed Acyclic Graph
- Kahn’s Algorithm for Topological Sorting
- Sum of dependencies in a graph
- Maximum Weight Node
Medium Problems
- Transitive Closure of a Graph using DFS
- Rotten Tomatoes
- Islands in a Graph
- Flood Fill
- Check for Bipartite
- Word Ladder
- Snakes and Ladder
- Water Jug problem
- Shortest Path in Binary Matrix
- Clone a Graph
- Detect Cycle in a Directed Graph
- Detect cycle in an Undirected graph
- Detect a negative cycle in a Graph | (Bellman Ford)
- Cycles of length n in an undirected and connected graph
- Detecting negative cycle using Floyd Warshall
- Clone a Directed Acyclic Graph
- Introduction to Disjoint Set Data Structure or Union-Find Algorithm
- Union By Rank and Path Compression in Union-Find Algorithm
- Dijkstra’s shortest path algorithm
- Bellman–Ford Algorithm
- Floyd Warshall Algorithm
- Johnson’s algorithm for All-pairs shortest paths
- Multistage Graph (Shortest Path)
- Karp’s minimum mean (or average) weight cycle algorithm
- Find minimum weight cycle in an undirected graph
- Prim’s Minimum Spanning Tree (MST)
- Kruskal’s Minimum Spanning Tree Algorithm
- Difference between Prim’s and Kruskal’s algorithm for MST
- Applications of Minimum Spanning Tree Problem
- Minimum cost to connect all cities
- Minimum Product Spanning Tree
- Reverse Delete Algorithm for Minimum Spanning Tree
- Boruvka’s algorithm for Minimum Spanning Tree
- Maximum edges that can be added to DAG so that is remains DAG
- Longest Path in a Directed Acyclic Graph
- Topological Sort of a graph using departure time of vertex
- Find Itinerary from a given list of tickets
- Eulerian path and circuit
- Fleury’s Algorithm for printing Eulerian Path or Circuit
- Strongly Connected Components
- Count all possible walks from a source to a destination with exactly k edges
- Euler Circuit in a Directed Graph
- Paths to travel each nodes using each edge (Seven Bridges of Königsberg)
- Length of shortest chain to reach the target word
- Dynamic Connectivity | Set 1 (Incremental)
- Max Flow Problem Introduction
- Ford-Fulkerson Algorithm for Maximum Flow Problem
- Find maximum number of edge disjoint paths between two vertices
- Maximum Bipartite Matching
- Channel Assignment Problem
- Karger’s Algorithm- Set 1- Introduction and Implementation
- Dinic’s algorithm for Maximum Flow
- Find length of the largest region in Boolean Matrix
- A Peterson Graph Problem
- Clone an Undirected Graph
- Graph Coloring (Introduction and Applications)
- Erdos Renyl Model (for generating Random Graphs)
- Chinese Postman or Route Inspection | Set 1 (introduction)
- Hierholzer’s Algorithm for directed graph
- Check whether a given graph is Bipartite or not
- Snake and Ladder Problem
- Boggle (Find all possible words in a board of characters)
- Hopcroft Karp Algorithm for Maximum Matching-Introduction
- Minimum Time to rot all oranges
- Construct a graph from given degrees of all vertices
- Determine whether a universal sink exists in a directed graph
- Number of sink nodes in a graph
- Two Clique Problem (Check if Graph can be divided in two Cliques)
Hard Problems
- Pacific Atlantic Water Flow
- Total number of Spanning Trees in a Graph
- Longest Path in a Directed Acyclic Graph
- Bridges in a graph
- Articulation Points (or Cut Vertices) in a Graph
- Biconnected Components
- Find if an array of strings can be chained to form a circle
- Tarjan’s Algorithm to find strongly connected Components
- Find minimum s-t cut in a flow network
- Traveling Salesman Problem (TSP) Implementation
- Vertex Cover Problem | Set 1 (Introduction and Approximate Algorithm)
- K Centers Problem | Set 1 (Greedy Approximate Algorithm)