← Back to mit.katmh.com

Depth-First Search

· Read 03/31/2021

Depth-First Search

  • Finds all vertices reachable from queried vertex ss 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 ss 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)
  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)(a,b) in relation to a DFS tree
  • Tree edge: part of DFS tree (parent[b] = a); bb discovered after aa and both haven't finished yet
  • Not a tree edge

    • Back edge: aa is a descendant of bb; bb already discovered but not finshed yet
    • Forward edge: bb is a descendant of aa; bb discovered after aa and finished before aa
    • Cross edge: neither are descendants of each other in the DFS tree; bb discovered and finished before aa 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