Data Structures

Graph Algorithms: BFS, DFS, Dijkstra

Цели урока

  • Master BFS and DFS
  • Find the shortest path (BFS and Dijkstra)
  • Implement topological sort
  • Understand when to use which algorithm

Предварительные знания

  • Graph fundamentals
  • Queues
  • Heaps
  • Graphs
  • Queues
  • Heaps

Google Maps finds a route among millions of roads in a second. npm knows in what order to install 1,000 packages. All of this comes down to graph algorithms.

  • Google Maps - shortest route between cities
  • npm/pip - dependency installation order
  • Social networks - degrees of separation between people
  • Compilers - module compilation order

BFS, DFS and Tarjan's algorithms

Breadth-first search came from Edward Moore in 1959 as a way to find the shortest path through a maze, with related ideas used by Edsger Dijkstra back in the 1950s. Depth-first search grew into a systematic tool thanks to Robert Tarjan in the early 1970s: building on it, he gave a linear-time algorithm for strongly connected components (SCC) in 1972 that is still treated as the model approach. Topological sorting, ordering the vertices of a directed acyclic graph, was formalised by Arthur Kahn in 1962. These classic traversals are the bedrock under the problems this lesson works through: connected components, dependency ordering, and reachability analysis.

BFS: Breadth-First Search

**BFS (Breadth-First Search):** traverse the graph level by level - first all neighbors, then neighbors of neighbors.

**BFS finds the shortest path** in an unweighted graph (minimum number of edges)!

BFS uses:

DFS: Depth-First Search

**DFS (Depth-First Search):** go as deep as possible, then backtrack.

CriterionBFSDFS
Data structureQueueStack / Recursion
Shortest pathYes (unweighted)No
MemoryO(width)O(depth)
Use casesShortest path, levelsCycles, connected

For detecting cycles in a graph it is better to use:

Shortest Path: BFS vs Dijkstra

Unweighted graph: BFS

Weighted graph: Dijkstra

**Dijkstra does not work with negative weights!** Use Bellman-Ford for those.

For a weighted graph with no negative weights we use:

Topological Sort

**Topological sort** - a linear ordering of vertices in a DAG such that for every edge u→v, u comes before v.

**Applications:** build order, task scheduling, dependency resolution in npm/pip.

Topological sort is possible for:

When to Use Which

  • **BFS:** shortest path (unweighted), level-by-level traversal
  • **DFS:** cycle detection, connectivity, topological sort
  • **Dijkstra:** shortest path (weighted, positive weights only)
  • **Topological Sort:** ordering tasks with dependencies

Next Topics

Graphs are a versatile tool. The next data structure helps work efficiently with dynamic connectivity.

  • Union-Find — Dynamic connectivity

Связанные уроки

  • ds-16-graphs-intro — Graph representation is needed before traversal or pathfinding
  • alg-14-dijkstra — Dijkstra is the canonical shortest-path algorithm shown here
  • alg-12-bfs — BFS finds shortest paths in unweighted graphs
  • alg-18-topological — Topological sort orders DAG vertices via DFS
  • ds-18-union-find — Union-Find tracks the connectivity that traversals reveal
  • net-30-bgp — Internet routing runs shortest-path search over a network graph
  • alg-13-dfs
Graph Algorithms: BFS, DFS, Dijkstra

0

1

Sign In