← Back to mit.katmh.com

# 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 = []
if parent[next] is None:
# iteration happens here
parent[next] = s
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 = []
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