Depth-First Search

Nikolay Kalinin | Harbour.Space, 24.03.2025

Undirected Graphs
● An undirected graph is an ordered pair G = (V, E), where V is a set of
vertices (nodes) and E is a set of 2-elements subsets of V called edges.
Usually, 0 < |V| < ∞. Edges are denoted as (u,v).
● Vertex degree is the number of adjacent vertices.
● Path is a sequence of vertices, connected consistently.
● V = {0, 1, 2, 3, 4, 5, 6}
● E = {(0,2), (0,6), (2,1), (2,6), (3,5)}
● d(0)=2, deg(1)=1, deg(2)=3, ...., deg(4)=0.
● [2,6,0,2,1] is a path.
Directed Graphs
● A directed graph is an ordered pair G = (V, E), where V is a set of vertices
(nodes) and E is a set of ordered pairs over V called edges (arcs).
Usually, 0 < |V| < ∞. Edges are denoted as (u,v).
● Vertex out-degree is the number of outgoing edges,
The in-degree is the number of ingoing edges.
● Path is a sequence of vertices, connected consistently.
● V = {0, 1, 2, 3, 4, 5}
● E = {(0,1), (1,2), (1,3), (2,0), (2,4), (4,2), (5,5)}
● out_d(0)=1, out_d(1)=2, out_d(3)=0, ..., out_d(5)=1.
in_deg(0)=in_deg(1)=1.
● [4,2,0,1,2] is a path.
Storing graphs
● Adjacency matrix: A[u][v]=1 if there is an edge (u, v).
○ O(n2) space. O(n) time to traverse adjacent vertices. O(1) time to check if an edge exists.
● Adjacency lists: edges[v] is a list (vector) of all edges from v.
○ O(m) space. O(d(v)) time to traverse adjacent vertices. O(d(v)) time to check if an edge exists.
Path Search Problem
● Given a graph G (directed or undirected) and two vertices s and t. Check if a
path from s to t exists? If a path exists, find and print any path from s to t.
● We need some strategy to traverse the graph, visiting all the vertices
reachable from s.
● Two popular strategies (algorithms): depth-first search (DFS) and breadth-first
search (BFS).
● DFS: explore the graph locally: in each step, we move to an unvisited
neighboring node. If there are none, we move back.
● BFS: explore the graph in all directions simultaneously, in parallel. Like fire or
flood spreads.
Path Tree
● A tree is a connected graph without cycles (considering undirected edges).
● The path tree is a tree rooted at s that covers all vertices reachable from s.
● Let parent[v] be the previous vertex on the path from s to v.
○ parent[s] = s,
○ parent[u] = None for unreachable vertices u.
● The parent array allows restoring the path from s to any vertex.

function pathTo(t):
path := []
while parent[t] != t:
path.push(t)
t = parent[t]
path.push(t)
reverse(path)
return path parent = [0,3,1,0,1,2,-1,-1,4]
Depth-first search (DFS)
● We define the dfs(cur) function that traverses all not-yet-visited vertices
reachable from cur without going through visited, and then returns.
● To do that, we check all unvisited neighbors to and call dfs(to) recursively.
● We have a global array to check is a vertex is visited.
● Running time is O(|V|+|E|).
To traverse the whole graph
function DFS(cur):
regardless of connectivity from s,
visited[cur] := true use a series of DFS calls:
for to in neighbors(cur):
visited[] ← false
if not visited[to]:
for s in V:
DFS(to) if not visited[s]:
DFS(s)
DFS: parents, three colors and in-out times
● Define three colors of vertices function DFS(cur, p):
○ WHITE: the vertex is not visited yet parent[cur] := p
○ GRAY: we entered the vertex, but not yet exited color[cur] := GRAY
(the call dfs(v) is in the stack) tin[cur] := T++
○ BLACK: we exited the vertex for to in neighbors(cur):
● visited[v] == (color[v] != WHITE) if color[to] == WHITE:
DFS(to, cur)
● The starting node s and the colors of all vertices
color[cur] := BLACK
are enough to continue the DFS tout[cur] := T++
● Define two values for each vertex
○ tin[v]: time when we entered v main:
(its color changes from WHITE to GRAY) parent[] ← -1
○ tout[v]: time when we exited v color[] ← WHITE
(its color changes from GRAY to BLACK) DFS(s, s)
DFS example
Example (s=0):
DFS example
Example (s=0):

⇒
Time Segments
● For any two vertices u and v, time segments [tin[u], tout[u]],
[tin[v], tout[v]] give the relation of u and v in the DFS-tree:
○ [tin[u], tout[u]] nested in [tin[v], tout[v]] denotes u being a descendant of v,

○ [tin[v], tout[v]] nested in [tin[u], tout[u]] is vice versa,

○ [tin[v], tout[v]] not intersecting [tin[u], tout[u]] denotes u and v being not
comparable.

○ No other case is possible.

Edge Types
● Group edges by the vertices color when we first look at the edge.
○ → Tree edges: from GRAY to WHITE
○ → Backward edges: from GRAY to GRAY
○ → Forward edges: from GRAY to BLACK, to a descendant
○ → Cross edges: from GRAY to BLACK, to a non-comparable
vertex
● To choose between forward or cross, look at the time segments.
● For undirected graphs, forward and cross edges do not exist, only tree and
backward edges exist.
Cycle Detection
● A cycle exists if and only if a backward edge exists, i.e. an edge from the
current vertex to a GRAY vertex (careful with undirected graphs: skip an edge
by which you came).
● For undirected graphs, visited/not visited information is enough, but skip the
parent edge.
● For directed graphs, three colors (WHITE, GRAY, BLACK) are required, no
need to skip the parent.
Topological Ordering
● A topological sorting or topological ordering of a directed graph is a linear
ordering of its vertices such that for every directed edge (u, v), u comes
before v in the ordering.
○ In other words, all edges go left to right.
● Possible topological orderings for graph on the right:
○ [e, h, g, c, b, f, a, d]
○ [g, h, c, e, b, f, d, a]
● Criterion: A topological ordering exists
if and only if the graph is acyclic.
Topological Ordering
● Naive approach. Each time extract a vertex u with in_deg(u)=0, append it
to the ordering, and remove from the graph.
● Linear algorithm. Run a DFS and order the vertices by decreasing of the
tout values.
function topsort(cur):
visited[cur] := true
for to in neighbors(cur):
if not visited[to]:
topsort(to)
order.append(u)

for s in V:
if not visited[s]:
topsort(s)
reverse(order)
Bipartite checking
● An undirected graph is bipartite, if we can color the vertices in two colors, so
that no edge connects two vertices of the same color
● A graph is bipartite if and only if it does not have a cycle of odd length
● Choose the color of any vertex and color the others with a DFS
● On any contradiction, break
● dfs(cur, cur_color):
if visited[cur]:
if color[cur] != cur_color: not bipartite
return
visited[cur] = True, color[cur] = cur_color
for to in neighbors(cur):
dfs(to, cur_color ^ 1)
Bridges
● For an undirected graph, a bridge is an edge of the graph whose deletion
increases the number of connected components.
● Criterion. An edge is a bridge if and only if it does not belong to any simple
cycle.
Bridges
● Let’s run a DFS.
● Only tree edges could be bridges.
● How to check if a tree edge is a bridge?
● Definition. Forward-up value, fup[u] is the smallest
depth we can reach from u by traversing zero or more
tree edges, at the end, zero or one backward edge.
● Depth d[v] is the distance from the root in tree edges.
Bridges
● Example

● fup = [0, 1, 3, 0, 1, 3, 1, 0, 3, 3].

Bridges
● Calculate fup values in O(|V|+|E|) using dynamic programming:
○ fup[v] is the minimum of fup over children of v, and depth over backward edges from v.
● function DFS(cur, parent, cur_depth):
visited[cur] := true
depth[cur] := fup[cur] := cur_depth
for to in neighbors(cur):
if to == parent:
Continue
if not visited[to]:
DFS(to, cur, cur_depth + 1)
fup[cur] := min(fup[cur], fup[to])
else:
fup[cur] := min(fup[cur], depth[to])
Bridges
●
● Tree edge (u,v) is a bridge if and only if there is no
edge from subtree of v to u or higher.
● In other words, tree edge (u,v) is a bridge if and only if
fup[v]>depth[u].
● We can check that after the return of the recursive call
from v.
● Linear algorithm to find all bridges.
Cut Vertices (Articulation Points)
● For an undirected graph, a cut vertex is a vertex of the graph whose deletion
increases the number of connected components.
● There is no simple connection between bridges and cut points!
Cut Vertices (Articulation Points)

● A vertex u is a cut point if and only if:

○ u is not the root and such tree edge (u,v)
exists that fup[v] ≥ dep[u],
○ u is the root and has at least 2 children in
the DFS-tree.
● Linear algorithm to find all cut vertices.
Strongly Connected Components
● A directed graph is strongly connected if
every vertex is reachable from every other
vertex.
● How to check if the given directed graph is
strongly connected in linear time?
● Run the DFS from any vertex s and check
that all vertices are reachable from s.
● Reverse the graph, run the DFS from the
same vertex s, and check that all vertices are
reachable.
Strongly Connected Components
● A strongly connected component (SCC) of a
directed graph is a maximal subgraph that is
strongly connected.
● There is a unique partition of a directed graph
into SCCs.
● There are several linear algorithms to find
strongly connected components.
Strongly Connected Components
● If each strongly connected component is
contracted to a single vertex, the resulting
graph is a directed acyclic graph called the
condensation of the original graph.
● A directed graph is acyclic if and only if it has
no strongly connected components with more
than one vertex.
Kosaraju's algorithm
● Run a series of DFS to visit all vertices. Order vertices in decreasing time of
their tout values.
○ This is exactly how a topological ordering algorithm works.
● Reverse the graph.
● Run a new series of DFS in the reversed graph. Choose the starting vertices
in the order obtained in the first step.
● Each DFS tree is a single strongly connected component.
● Strongly connected components are found in a topological order.
○ No need to run another topsort on the SCCs.
DFS is a deep recursion
● In most OS and programming languages, recursion is limited, because the
stack size is limited
● The standard implementation of DFS is recursion-heavy, so it can cause stack
overflow (or hit the recursion limit)
● For C++ on Windows add -Wl,--stack=256000000 when compiling
● For Linix, use ulimit -s 256000000 before running
● In python, use sys.setrecursionlimit(5000000)
● In production code implement recursion manually with a stack, or switch to
BFS