What topics does this roadmap cover?

Graph Fundamentals, Depth First Search (DFS), Breadth First Search (BFS), Flood Fill & Grid Graphs, Bipartite Graphs, Tree Fundamentals, Tree Diameter & Center, Subtree DP, Floyd-Warshall Algorithm, Dijkstra's Algorithm, Bellman-Ford Algorithm, Mixed Practice - Shortest Paths, Disjoint Set Union (DSU), Minimum Spanning Trees, Topological Sort, DP on DAGs, Mixed Practice: Graph Traversals, Strongly Connected Components, 2-SAT, Mixed Practice: Connectivity & MST, Rerooting Technique, Euler Tour Technique, Mixed Practice: Tree Fundamentals, Binary Lifting, Lowest Common Ancestor (LCA), Games on Graphs, Heavy-Light Decomposition, Centroid Decomposition, Small-to-Large Merging, Functional Graphs, Mixed Practice: Advanced Tree Techniques, Bridges and Articulation Points, Network Flow, Maximum Bipartite Matching, Minimum Cut, Euler Paths and Circuits, Mixed Practice: Advanced Graphs

How many units are in this roadmap?

This roadmap contains 1633 units across 37 sections.

Is this roadmap free?

Yes, this roadmap is completely free.

Graph Theory - Roadmaps

Minimum Cut

You've mastered max flow. Now learn minimum cuts: the cheapest way to disconnect source from sink.

Intro

(Splitting networks)

What is a Cut?

(Partitioning vertices)

Cut Capacity

(Sum of crossing edges)

s-t Cut

(Source and sink separation)

Minimum s-t Cut

(Cheapest way to disconnect)

Max-Flow Min-Cut Theorem

(Flow equals cut capacity)

Theorem Intuition

(Why flow equals cut)

Quiz: Max-Flow Min-Cut Relationship

Knowledge check

Finding the Min Cut

Using max flow residual graph

Algorithm - Find Min Cut

(Step by step)

Why Residual Graph Works

(No augmenting paths left)

Example - Finding Min Cut

(Small network)

Quiz: Finding Cut Edges

Knowledge check

Global Minimum Cut

(No source or sink)

Stoer-Wagner Algorithm

(Finding global min cut)

Edge Connectivity

(Minimum edges to disconnect)

Vertex Connectivity

Minimum vertices to disconnect

Application - Network Reliability

(Finding weak points)

Application - Image Segmentation

(Foreground and background)

Application - Clustering

(Splitting data into groups)

Quiz: Stoer-Wagner Algorithm

Knowledge check

Problem - Police Chase

(CSES 1695)

Problem - Police Chase - Read Statement

(CSES 1695)

Core Idea - Max Flow with Unit Capacities

(Flow equals number of roads)

Core Idea - Extracting the Cut Edges

(Which roads to block)

Handling Bidirectional Roads

(Each road becomes two edges)

Implementation - Police Chase

(Pseudocode)

Implementation - Police Chase - Implement Solution

(CSES 1695)

Lessons - Min Cut Applications

(Real-world uses)

Quiz: Vertex vs Edge Connectivity

Knowledge check

Problem - Distinct Routes

(CSES 1711)

Problem - Distinct Routes - Read Statement

(CSES 1711)

Core Idea - Max Flow Equals Path Count

(Edge-disjoint paths)

Core Idea - Flow Decomposition

(Extracting paths from flow)

Algorithm - Path Decomposition

(Trace and subtract)

Implementation - Distinct Routes

(Pseudocode)

Implementation - Distinct Routes - Implement Solution

(CSES 1711)

Lessons - Flow Decomposition

(Paths from flow)

Problem - Network Segmentation

(Custom problem)

Core Idea - Try All Pairs

(Brute force approach)

Core Idea - Stoer-Wagner Basics

(Contracting vertices)

Maximum Adjacency Ordering

(Picking vertices to cut)

Algorithm - Stoer-Wagner

(Step by step)

Quiz: Maximum Adjacency Ordering

Knowledge check

Implementation - Network Segmentation

(Pseudocode for Stoer-Wagner)

Lessons - Global vs Local Cuts

(Different problem types)

Section Recap

(What you learned)

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/graph-theory

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████████████████████████████████████