DEV Community

Dev Cookies
Dev Cookies

Posted on

📚 Mastering Graphs: Pattern-Based Blog Series

Blog 1: Graph Fundamentals & Representations

  • Adjacency List, Adjacency Matrix, Edge List.
  • Directed vs Undirected, Weighted vs Unweighted.
  • BFS/DFS basics on graphs.
  • Snippet: build graph in Java using adjacency list.

Blog 2: BFS Pattern (Level Order, Shortest Path in Unweighted Graphs)

  • BFS traversal explained.
  • Shortest path in unweighted graph.
  • Classic Problems: Rotten Oranges, Word Ladder, Minimum Steps in Grid.
  • Snippet: BFS with queue.

Blog 3: DFS Pattern (Path Exploration, Connectivity, Components)

  • DFS recursive & iterative.
  • Connected components.
  • Detecting cycles with DFS.
  • Problems: Number of Islands, Graph Coloring.
  • Snippet: DFS recursion & stack-based.

Blog 4: Topological Sort & DAG Problems

  • Kahn’s Algorithm (BFS).
  • DFS-based topological ordering.
  • Problems: Course Schedule, Task Scheduling.
  • Snippet: Topo sort with indegree array.

Blog 5: Shortest Path Algorithms

  • BFS (unweighted).
  • Dijkstra’s (weighted, positive).
  • Bellman-Ford (handles negative edges).
  • Floyd-Warshall (all pairs).
  • Problems: Network Delay Time, Cheapest Flights with K Stops.

Blog 6: Minimum Spanning Tree (MST)

  • Kruskal’s (Union-Find).
  • Prim’s (Min Heap).
  • Applications: Network design, clustering.
  • Problems: Connecting Cities with Minimum Cost.

Blog 7: Union-Find / Disjoint Set Pattern

  • DSU implementation.
  • Path compression & union by rank.
  • Detect cycle in undirected graph.
  • Problems: Redundant Connection, Accounts Merge.

Blog 8: Strongly Connected Components & Bridges/Articulation Points

  • Kosaraju’s algorithm.
  • Tarjan’s algorithm (low-link values).
  • Bridges in graph (critical connections).
  • Problems: Critical Connections in Network, SCC counting.

Blog 9: Advanced Graph Patterns (Flow, Matching, Bipartite)

  • Bipartite check with BFS/DFS.
  • Max Flow (Ford-Fulkerson, Edmonds-Karp).
  • Bipartite Matching.
  • Problems: Maximum Bipartite Matching, Water Distribution.

Blog 10: Advanced Graph Tricks & Real-World Applications


⚡ By the end, you’ll have a Graph Pattern Playbook like we built for backtracking — covering all traversals, connectivity, shortest paths, MST, SCC, Union-Find, and advanced flow problems.

Top comments (0)