Depth-First Search

• Finds all vertices reachable from queried vertex $s$ by searching undiscovered vertices as deep as possible before exploring other branches

• Returns a DFS tree, formed by a set of parent pointers for verties reachable from $s$ in the order the search discovered them

  • Unlike a BFS tree, a DFS tree does not represent shortest paths in an unweighted graph
• Best implemented recursively (whereas BFS is done by maintaining a queue, dequeueing a node, and checking all univisited neighbors)

def dfs(Adj, s, parent=None, order=None):
  if parent is None:
    parent = [None for v in Adj]
    parent[s] = s
    order = []
  for next in Adj[s]:
    if parent[next] is None:
      # iteration happens here
      parent[next] = s
      dfs(Adj, next, parent, order)
  order.append(s)
  return parent, order

• (From pset 6.1.1) An iteration of DFS can be thought of as when we call DFS on an unexplored vertex, or when we update the parent list

  • For me, the former makes more sense because each iteration corresponds to a vertex to query

Full Graph Exploration

• To search all vertices in a graph, perform DFS (or BFS) from each vertex in the graph that has not yet been discovered
• This enables us to explore each connected component in the graph, and it's conceptually equivalent to adding a vertex with an outgoing edge to every node in the graph, then running DFS/BFS from that vertex

def graph_explore(Adj):
  parent = [None for v in Adj]
  order = []
  for v in range(len(Adj)):
    if parent[v] is None:
      parent[v] = v # root
      dfs(Adj, v, parent, order) # DFS from v (BFS can also be used)
  return parent, order

• For historical reasons (connection to topsort), DFS refers to both a method to search a graph from a specific vertex and a method to search an entire graph

DFS Edge Classification

• Classify edges $(a,b)$ in relation to a DFS tree
• Tree edge: part of DFS tree (parent[b] = a); $b$ discovered after $a$ and both haven't finished yet

• Not a tree edge

  • Back edge: $a$ is a descendant of $b$; $b$ already discovered but not finshed yet
  • Forward edge: $b$ is a descendant of $a$; $b$ discovered after $a$ and finished before $a$
  • Cross edge: neither are descendants of each other in the DFS tree; $b$ discovered and finished before $a$ discovered and finished

• Facts from exercises

  • Forward and cross edges cannot occur in undirected graph; they would've been explored in other direction first as back or tree edges
  • If graph has back edge, must have cycle