Graphs: Depth‐First Search - rFronteddu/general_wiki GitHub Wiki

Depth-first Search (DFS) is an algorithm that explores the edges of a graph by moving along the most recently discovered vertex with unexplored edges. Once all edges of that vertex are explored, the algorithm "backtracks" to the previous vertex. This process repeats until all reachable vertices from the original source have been discovered. If there are still undiscovered vertices, DFS selects one of them as a new source and starts the process again, continuing until every vertex is discovered.

Unlike Breadth-First Search (BFS), which generates a single tree from the source, DFS can produce multiple trees, forming a structure called a depth-first forest.

Predecessor Subgraph The predecessor subgraph from DFS, denoted as $G_p=(V,E_p)$, where $E_p$ contains edges (v.p,v) for each vertex $v \in V$, forms the depth-first forest. These edges are called tree edges.

Timestamps DFS assigns two timestamps to each vertex v:

• Discovery time (v.d): Marks when a vertex is first discovered (colored gray).
• Finishing time (v.f): Marks when the search finishes examining v's adjacency list (colored black).

For each vertex u, it holds that u.d < u.f, and vertices change color during the search:

• White before u.d,
• Gray between u.d. and u.f,
• Black after u.f.

Algorithm

// the cost is O(V+E)
DFS(G)
    for each vertex u in G.V
        u.color = WHITE
        u.p = nil
    global time = 0
    for each vertex u in G.V
        if u.color == WHITE
            DFS-VISIT(G, u)

DFS-VISIT(G, u)
    u.d = ++time
    u.color = GRAY
    for each v in G.Adj[u]
        if v.color == WHITE
            v.p = u
            DFS-VISIT(G,v)
    u.color = BLACK
    u.f = ++time

Parenthesis theorem

A key property of DFS is that discovery and finishing times form a well-nested sequence of parentheses. If the discovery of vertex u is represented by (u and its finishing by u), then the sequences of discoveries and finishes is always properly nested. For any two vertices u and v in the graph, exactly one of the following conditions holds:

• The intervals [u.d, u.f] and [v.d, v.f] are disjoint, and neither u nor v is a descendant of the other.
• [u.d, u.f] is entirely contained within [v.d, v.f], and u is a descendant of v.
• [v.d, v.f] is entirely contained within [u.d, u.f] and v is a descendant of u.

Edge Classification

DFS allows for the classification of edges based on their role in the depth-firs forest:

• Tree edges: Part of the depth-first forest, discovered while exploring a vertex.
• Black edges: Connect a vertex to one of its ancestors in the depth-first forest.
• Forward edges: Connect a vertex to a descendant in the same depth-first tree, but are not tree edges.
• Cross edges: Connect vertices in different trees or within the same tree without an ancestor-descendant relationship.

The color of the destination vertex during edge exploration helps classify the edge:

• White: Tree edge,
• Gray: Back edge,
• Black: Forward or cross edge.

In an undirected graph, all edges are either tree edges or black edges.