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. 3.3 covered implementing graph traversals using queues and stacks, but also covered the different ways to represent graphs themselves.

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

Concepts:

• Node m is an ancestor of node n if n was marked as explored after m (I think)
• If x & y are two nodes that are connected by an edge in the original graph, but not connected its BFS tree, one of them is an ancestor of the other

Runtime: O(

There are 2 basic ways to represent graphs:

1. An adjacency matrix – requires O(n^2 ) space
2. An adjacency list representation – requires only O(m+n) space

A queue is a set form which we extract elements in FIFO (first in, first out) order = the order in which they were added

• Stack = same, but opposite (LIFO)

3.2 was surprisingly easy to read. I liked all the examples equating BFS and DFS to navigating a kind of maze of hallways and rooms.