# Graph Study Guide :::warning [< Return to Home Page](https://hackmd.io/@siansiansu/HknJJm0W0) ::: ## Graph Representation and Traversal #### HashMap - 🟨 [133\. Clone Graph](https://leetcode.com/problems/clone-graph/) \[[Solution](https://hackmd.io/@siansiansu/H1bSb6rQ0)\] ### Connected Components #### Union Find - 🟨 [261\. Graph Valid Tree](https://leetcode.com/problems/graph-valid-tree/) \[[Solution](https://hackmd.io/@siansiansu/Bkt6f187A)\] - 🟨 [323\. Number of Connected Components in an Undirected Graph](https://leetcode.com/problems/number-of-connected-components-in-an-undirected-graph/) \[[Solution](https://hackmd.io/@siansiansu/SyzDRUDSR)\] - 🟨 [547\. Number of Provinces](https://leetcode.com/problems/number-of-provinces/) \[[Solution](https://hackmd.io/@siansiansu/SyE6EWAtC)\] - 🟨 [684\. Redundant Connection](https://leetcode.com/problems/redundant-connection/) \[[Solution](https://hackmd.io/@siansiansu/rJTNvPJQ0)\] - 🟧 [721\. Accounts Merge](https://leetcode.com/problems/accounts-merge/) \[[Solution](https://hackmd.io/@siansiansu/Skrch9JcR)\] Graph Search Algorithms ----------------------- ### Depth-First Search (DFS) - 🟨 [200\. Number of Islands](https://leetcode.com/problems/number-of-islands/) \[[Solution](https://hackmd.io/@siansiansu/B18n_SofA)\] - 🟨 [695\. Max Area of Island](https://leetcode.com/problems/max-area-of-island/) \[[Solution](https://hackmd.io/@siansiansu/SJFWe8sG0)\] - 🟩 [733\. Flood Fill](https://leetcode.com/problems/flood-fill/) \[[Solution](https://hackmd.io/@siansiansu/HJaQ8UvGC)\] ### Breadth-First Search (BFS) - 🟥 [127\. Word Ladder](https://leetcode.com/problems/word-ladder/) - 🟨 [542\. 01 Matrix](https://leetcode.com/problems/01-matrix/) \[[Solution](https://hackmd.io/@siansiansu/BkUIeELQC)\] - 🟨 [909\. Snakes and Ladders](https://leetcode.com/problems/snakes-and-ladders/) \[[Solution](https://hackmd.io/@siansiansu/rJFDA2xr0)\] - 🟨 [994\. Rotting Oranges](https://leetcode.com/problems/rotting-oranges/) \[[Solution](https://hackmd.io/@siansiansu/HylCtLof0)\] ### Special Search Problems - 🟨 [417\. Pacific Atlantic Water Flow](https://leetcode.com/problems/pacific-atlantic-water-flow/) \[[Solution](https://hackmd.io/@siansiansu/HyGiiIUXC)\] - 🟨 [130\. Surrounded Regions](https://leetcode.com/problems/surrounded-regions/) \[[Solution](https://hackmd.io/@siansiansu/SyKjBXkNR)\] - 🟥 [329\. Longest Increasing Path in a Matrix](https://leetcode.com/problems/longest-increasing-path-in-a-matrix/) - 🟨 [863\. All Nodes Distance K in Binary Tree](https://leetcode.com/problems/all-nodes-distance-k-in-binary-tree/) - 🟨 [1197\. Minimum Knight Moves](https://leetcode.com/problems/minimum-knight-moves/) - 🟨 [1730\. Shortest Path to Get Food](https://leetcode.com/problems/shortest-path-to-get-food/) Shortest Path Problems ---------------------- ### Single Source Shortest Path (SSSP) - 🟨 [743\. Network Delay Time](https://leetcode.com/problems/network-delay-time/) - 🟨 [787\. Cheapest Flights Within K Stops](https://leetcode.com/problems/cheapest-flights-within-k-stops/) ### All Pairs Shortest Path #### Floyd–Warshall Algorithm - 🟨 [1334\. Find the City With the Smallest Number of Neighbors at a Threshold Distance](https://leetcode.com/problems/find-the-city-with-the-smallest-number-of-neighbors-at-a-threshold-distance/) \[[Solution](https://hackmd.io/@siansiansu/B1lxSUbKA)\] #### Bellman-Ford Algorithm #### Minimum Spanning Tree (MST) - 🟨 [1135\. Connecting Cities With Minimum Cost](https://leetcode.com/problems/connecting-cities-with-minimum-cost/) - Prim's Algorithm - Kruskal's Algorithm #### Topological Sorting - 🟥 [269\. Alien Dictionary](https://leetcode.com/problems/alien-dictionary/) - 🟨 [207\. Course Schedule](https://leetcode.com/problems/course-schedule/) - 🟨 [210\. Course Schedule II](https://leetcode.com/problems/course-schedule-ii/) - 🟨 [310\. Minimum Height Trees](https://leetcode.com/problems/minimum-height-trees/) Directed Graph Problems ----------------------- - 🟨 [399\. Evaluate Division](https://leetcode.com/problems/evaluate-division/) \[[Solution](https://hackmd.io/@siansiansu/B12ozV1VC)\] Advanced Graph Topics --------------------- - 🟥 [1192\. Critical Connections in a Network](https://leetcode.com/problems/critical-connections-in-a-network/) - Strongly Connected Components (SCC) - Tarjan's Algorithm - Kosaraju's Algorithm - Eulerian Path - Travelling Salesman Problem (TSP) - Hamiltonian Path Problem Difficulty Legend ------------------------- - 🟩 Easy - 🟨 Medium - 🟧 Medium-Hard - 🟥 Hard - ⬛ Very Hard Additional Resources -------------------- - [Introduction to Graph Theory (Video)](https://www.youtube.com/watch?v=HmQR8Xy9DeM) - [Graph Algorithms for Technical Interviews](https://www.youtube.com/watch?v=tWVWeAqZ0WU) - [Graph Theory and Algorithms (MIT OpenCourseWare)](https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-science-fall-2010/readings/MIT6_042JF10_chap05.pdf)