Graph Algorithms

Graph problems describe things and the links between them, such as cities and roads, or courses and their prerequisites in Course Schedule. Once you can see the graph, most questions come down to a known algorithm.

The nine chapters cover traversal, topological sort, shortest paths, minimum spanning trees, Eulerian paths, strongly and biconnected components, bipartite coloring, network flow, and miscellaneous graph problems. It is the last plan on the route and assumes you are comfortable with recursion and BFS.

109 problemsRating 1383–30289 Chapters

Open the study room

Want company while you work through this list? Sign in, open the study room, and your heroine will bring you the problems one at a time.

I. Graph Traversal

§1.1 Depth-First Search (DFS)

Problem	Rating
547. Number of Provinces	1383
1971. Find If Path Exists in Graph	1397
797. All Paths From Source to Target	1383
1306. Jump Game III	1397
841. Keys AND Rooms	1412
2316. Count Unreachable Pairs of Nodes in an Undirected Graph	1604
1319. Number of Operations to Make Network Connected	1633
2492. Minimum Score of a Path Between Two Cities	1680
3310. Remove Methods From Project	1711
2685. Count the Number of Complete Components	1769
2192. All Ancestors of a Node in a Directed Acyclic Graph	1788
3387. Maximize Amount After Two Days of Conversions	1788
924. Minimize Malware Spread	1869
2101. Detonate the Maximum Bombs	1880
721. Accounts Merge	Unrated
207. Course Schedule	Unrated
802. Find Eventual Safe States	1962
3695. Maximize Alternating Sum Using Swaps	1984
928. Minimize Malware Spread II	1985
2092. Find All People with Secret	2004

§1.2 Breadth-First Search (BFS)

Problem	Rating
3243. Shortest Distance After Road Addition Queries I	1568
1311. Get Watched Videos by Your Friends	1653
3015. Count the Number of Houses at a Certain Distance I	1658
1129. Shortest Path with Alternating Colors	1780
2039. The Time When the Network Becomes Idle	1865
2608. Shortest Cycle in a Graph	1904
815. Bus Routes	1964

§1.3 Modeling + BFS Shortest Path

Problem	Rating
433. Minimum Genetic Mutation	Unrated
1284. Minimum Number of Flips to Convert Binary Matrix to Zero Matrix	1811
773. Sliding Puzzle	1815
752. Open the Lock	1878
301. Remove Invalid Parentheses	Unrated
514. Freedom Trail	Unrated
847. Shortest Path Visiting All Nodes	2201
854. K Similar Strings	2377
127. Word Ladder	Unrated
488. Zuma Game	Unrated

II. Topological Sort

§2.1 Topological Sort

Problem	Rating
210. Course Schedule II	Unrated
2115. Find All Possible Recipes From Given Supplies	1679
2392. Build a Matrix with Conditions	1961
802. Find Eventual Safe States	1962
1591. Strange Printer II	2291
1203. Sort Items by Groups Respecting Dependencies	2419
2603. Collect Coins in a Tree	2712

§2.2 DP on Topological Order

Problem	Rating
851. Loud AND Rich	1783
2050. Parallel Courses III	2084
1857. Largest Color Value in a Directed Graph	2313

§2.3 Pseudotrees (Functional Graphs)

Problem	Rating
2359. Find Closest Node to Given Two Nodes	1715
2360. Longest Cycle in a Graph	1897
684. Redundant Connection	Unrated
685. Redundant Connection II	Unrated
2876. Count Visited Nodes in a Directed Graph	2210
2127. Maximum Employees to Be Invited to a Meeting	2449
2836. Maximize Value of Function in a Ball Passing Game	2769

III. Shortest Paths

§3.1 Single Source Shortest Path (Dijkstra)

Problem	Rating
743. Network Delay Time	Unrated
3341. Find Minimum Time to Reach Last Room I	1721
3112. Minimum Time to Visit Disappearing Nodes	1757
2642. Design Graph with Shortest Path Calculator	1811
3604. Minimum Time to Reach Destination in Directed Graph	1845
1514. Path with Maximum Probability	1846
3650. Minimum Cost Path with Edge Reversals	1854
3342. Find Minimum Time to Reach Last Room II	1862
1786. Number of Restricted Paths From First to Last Node	2079
3123. Find Edges in Shortest Paths	2093
1976. Number of Ways to Arrive at Destination	2095
2662. Minimum Cost of a Path with Special Roads	2154
3377. Digit Operations to Make Two Integers Equal	2186
2045. Second Minimum Time to Reach Destination	2202
882. Reachable Nodes in Subdivided Graph	2328
2203. Minimum Weighted Subgraph with the Required Paths	2364
2577. Minimum Time to Visit a Cell in a Grid	2382
818. Race Car	2392
1928. Minimum Cost to Reach Destination in Time	2413
787. Cheapest Flights Within K Stops	Unrated
2699. Modify Graph Edge Weights	2874

§3.2 All-Pairs Shortest Path (Floyd-Warshall)

Problem	Rating
2642. Design Graph with Shortest Path Calculator	1811
1334. Find the City with the Smallest Number of Neighbors at a Threshold Distance	1855
2976. Minimum Cost to Convert String I	1882
2959. Number of Possible Sets of Closing Branches	2077
2977. Minimum Cost to Convert String II	2696

IV. Minimum Spanning Tree (MST)

Problem	Rating
1584. Min Cost to Connect All Points	1858
1489. Find Critical AND Pseudo Critical Edges in Minimum Spanning Tree	2572

V. Eulerian Path & Circuit

Problem	Rating
332. Reconstruct Itinerary	Unrated
753. Cracking the Safe	2274
2097. Valid Arrangement of Pairs	2651

VI. Connected Components (SCC/BCC)

VI. Strongly / Biconnected Components

Problem	Rating
1192. Critical Connections in a Network	2085
1568. Minimum Number of Days to Disconnect Island	2209

VII. Bipartite Coloring

Problem	Rating
785. Is Graph Bipartite	1625
886. Possible Bipartition	1795

VIII. Network Flow

Problem	Rating
1947. Maximum Compatibility Score Sum	1704
3376. Minimum Time to Break Locks I	1793
2850. Minimum Moves to Spread Stones Over Grid	2001
1879. Minimum XOR Sum of Two Arrays	2145
1349. Maximum Students Taking Exam	2386
2172. Maximum AND Sum of Array	2392
3276. Select Cells in Grid with Maximum Score	2403
1595. Minimum Cost to Connect Two Groups of Points	2538
3257. Maximum Value Sum by Placing Three Rooks II	2553

IX. Miscellaneous Graph Algorithms

IX. Miscellaneous

Problem	Rating
1042. Flower Planting with No Adjacent	1712
1761. Minimum Degree of a Connected Trio in a Graph	2005
2508. Add Edges to Make Degrees of All Nodes Even	2060
1579. Remove Max Number of Edges to Keep Graph Fully Traversable	2132
2065. Maximum Path Quality of a Graph	2178
1697. Checking Existence of Edge Length Limited Paths	2300
2242. Maximum Score of a Node Sequence	2304
2493. Divide Nodes Into the Maximum Number of Groups	2415
1782. Count Pairs of Nodes	2457
3666. Minimum Operations to Equalize Binary String	2477
2612. Minimum Reverse Operations	2824
3435. Frequencies of Shortest Supersequences	3028
466. Count the Repetitions	Unrated

This is the final plan on the route; after its core sections, your heroine moves on to the advanced lists, where the optional sections from earlier plans wait.

Ratings come from zerotrac's LeetCode contest ratings. Some problems have no zerotrac rating and are marked Unrated.

Open the study room