Data Structures and Algorithms · Graphs

Graph traversal (BFS and DFS)

Visiting every reachable vertex, either level by level (BFS) or by diving deep first (DFS).

Also known as: breadth-first search, depth-first search, connected components.

Start a lesson on Graph traversal (BFS and DFS)

Learn first

• Graph representations: Storing a graph's vertices and edges as an adjacency matrix or adjacency list.
• Stacks and queues: Two restricted-access orderings, last-in-first-out and first-in-first-out.

Leads to

• Topological sort: Ordering the vertices of a directed acyclic graph so every edge points forward.
• Dijkstra's algorithm: Finding the cheapest path from one vertex to all others when no edge weight is negative.
• Bellman-Ford algorithm: Finding shortest paths that still works when some edge weights are negative, at the cost of speed.

Related topics

• Topological sort: Ordering the vertices of a directed acyclic graph so every edge points forward.
• Backtracking: Trying a choice, recursing, and undoing it if it leads nowhere, to explore all possibilities.