3.2-3.6:

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.

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

Worst-case runtime: O(# of vertices)

General concept: start from s and try the first edge leading out. Continue this process until you reach a “dead end” = a node for which you had already explored all its neighbors. Then backtrack until you get a node with an unexplored neighbor and continue from there. Pseudocode:

  DFS(u):
      Mark u as "Explored" and add u to R
      For each edge (u,v) incedent to u
          If v is not marked "Explored" then
              Recursively invoke DFS(v)
          Endif
      Endfor