Library/Combinatorics/Graph Theory/Graph traversal

Graph traversal

Overview
Important

Graph traversal is the process of systematically visiting all the vertices (and sometimes edges) of a graph. The two most common traversal algorithms are Depth-First Search (DFS) and Breadth-First Search (BFS).

Important properties

  • DFS explores as far as possible along each branch before backtracking.

  • BFS explores all neighbors of a vertex before moving to the next level.

  • Both methods can be used to check if a graph is connected, find paths, or search for specific vertices.

  • Traversal can be implemented using recursion or with data structures like stacks (DFS) and queues (BFS).