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. 3.4 covered an application of BFS that tested bipartness, and 3.5 covered connectivity in directed graphs. Overall, this section wasn't too difficult for me, as it was pretty readable. However, it did admittedly get progressively more difficult. I honestly think I need more time to let it all sink in before I can conjure up concrete questions to ask.

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

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)