Handbook of Graph Theory, 2nd Edition

Chapter 10

Graphs in Computer Science

Section 10.1 Searching

Harold N. Gabow

University of Colorado

Introduction

A search of a graph is a methodical exploration of all the vertices and edges. It must run in “linear time,” i.e., in one pass (or a small number of passes) over the graph. Even with this restriction, a surprisingly large number of fundamental graph properties can be tested and identified.

This section examines the two most important search methods. Breadth-first search gives an efficient way to compute distances. Depth-first search is useful for checking many basic connectivity properties, for checking planarity, and also for data flow analysis for compilers. A treatment of at least some aspects of both these methods can be found ...