This is an old revision of the document!
Table of Contents
3.2-3.6:
Brief summary
3.2 covered graph connectivity and graph traversal, including breadth-first and depth-first searches, which determine s-t connectivity, or whether or not there is a path between s and t in a given graph.
Motivations
Algorithms: brief sketches, intuitions, implementations, runtimes
Breadth-First Search
Explore outward from s in all possible directions, adding nodes one “layer” at a time. Layers
- The layer containing a node represents the point in time at which the node is reached.
- The first layer of the search is all neighboring nodes of s (nodes that are joined by an edge to s)
- Generally speaking, Layer #j+1 contains all nodes that do not belong to an earlier layer and that have an edge to a node in layer #j
Concepts:
- There is a path from s to t IFF t appears in some layer
- If there is an edge between two points in the original graph, then those two points differ by at most 1 in the breadth-first search tree
