AlgoViz
HomeGraphs

Graphs

Nodes and edges — traversal, shortest paths, connectivity.

0/ 61 understood · 0%
Walkthroughs
57
Problems
61
Start here
61 shown
  1. OverviewDirected, weighted, and how we store themMedium
  2. Course ScheduleCan you finish? = is it a DAG (no cycle)?Medium
  3. Number of IslandsFlood-fill each unvisited land cellMedium
  4. Union-Find (DSU)Disjoint sets · find + unionMedium
  5. Practice problems
  6. Introduction to GraphVertices, edges, and the choices that matterEasy
  7. Graph RepresentationAdjacency list or adjacency matrixEasy
  8. Connected ComponentsCount how many traversals it takesMedium
  9. Traversal TechniquesBFS explores in rings, DFS divesMedium
  10. DFSRecurse into unvisited neighboursMedium
  11. Number of provincesConnected components of a friendship matrixMedium
  12. Connected Components Problem in MatrixIslands, counted by traversalMedium
  13. Rotten OrangesMulti-source BFS, one minute per levelMedium
  14. Flood fill algorithmRepaint the connected regionMedium
  15. Cycle Detection in Undirected Graph (bfs)A visited neighbour that is not your parentHard
  16. Detect a cycle in an undirected graphSame rule, DFS or union-findHard
  17. Distance of nearest cell having oneMulti-source BFS from every 1Medium
  18. Surrounded RegionsMark what touches the border, flip the restMedium
  19. Number of enclavesRemove border-reachable land, count what remainsMedium
  20. Word ladder IBFS over words differing by one letterHard
  21. Word ladder IIBFS for distances, then DFS to rebuild pathsHard
  22. Bipartite Graph (DFS)Two-colour the graph; a clash means not bipartiteHard
  23. Cycle Detection in Directed Graph (DFS)A back edge into the current recursion pathHard
  24. Topo SortOrder nodes so every arrow points forwardHard
  25. Topological sort or Kahn's algorithmPeel off zero-in-degree nodes into an orderHard
  26. Detect a cycle in a directed graphRecursion stack, or a failed topological sortHard
  27. Course Schedule IFinishable exactly when there is no cycleHard
  28. Course Schedule IIKahn's algorithm, keeping the orderMedium
  29. Find eventual safe statesReverse the edges and run Kahn'sHard
  30. Alien DictionaryCompare adjacent words for one ordering factHard
  31. Shortest path in undirected graph with unit weightsBFS gives distances directlyHard
  32. Shortest path in DAGTopological order lets you relax each edge onceHard
  33. Djisktra's AlgorithmGreedy shortest paths with non-negative weightsHard
  34. Why priority Queue is used in Djisktra's AlgorithmThe heap hands you the nearest node instantlyHard
  35. Shortest Distance in a Binary MazeBFS across open cellsHard
  36. Path with minimum effortDijkstra where cost = the biggest single stepHard
  37. Cheapest flight within K stopsBellman-Ford capped at k+1 roundsHard
  38. Network Delay TimeDijkstra, then take the farthest arrivalMedium
  39. Number of ways to arrive at destinationDijkstra that also counts shortest routesHard
  40. Minimum multiplications to reach endBFS over the 100000 residuesHard
  41. Bellman Ford AlgorithmRelax all edges V-1 times; handles negativesHard
  42. Floyd warshall algorithmAll-pairs shortest paths by trying every middle nodeHard
  43. Find the city with the smallest number of neighborsFloyd-Warshall, then count close neighboursHard
  44. MST theoryConnect every node for the least total weightEasy
  45. Prim's AlgorithmGrow the tree by its cheapest outgoing edgeHard
  46. Disjoint SetUnion by rank plus path compressionHard
  47. Find the MST weightKruskal: sort edges, skip the cyclesHard
  48. Number of operations to make network connectedComponents minus one, if you have spare cablesHard
  49. Most stones removed with same row or columnEach component leaves one stone behindMedium
  50. Accounts mergeUnion accounts through shared emailsHard
  51. Number of islands IIUnion-find as the land appearsHard
  52. Making a large islandLabel the islands, then test each zeroHard
  53. Swim in Rising WaterDijkstra where cost = the highest cell so farMedium
  54. Bridges in graphTarjan: compare discovery and low-link timesHard
  55. Articulation point in graphThe same low-link test, one comparison looserHard
  56. Kosaraju's algorithmOrder by finish time, then search the reverse graphHard
  57. Shortest Path AlgorithmsPick the right shortest-path toolMedium
  58. Cheapest Flights Within K StopsBellman-Ford capped at k+1 roundsMedium
  59. Find the City With Fewest ReachableFloyd-Warshall, then find the loneliest cityMedium
  60. Number of Connected ComponentsTraverse from each unvisited nodeMedium
  61. Redundant ConnectionThe edge that closes a cycleMedium
  62. Word LadderShortest path in a word graphMedium