DFS
Notes
- Breadth first search uses a queue to explore the graph in rings going away from the start.
- Depth first uses a stack, (Recursive call) to get as far away from the start as possible.
- Input as before
- We will use π and color as before
- They introduce d and f as the discovery and finishing time.
- We will use these in topological sort later.
- They don't give a start node, but we can discuss how to accomplish this as well.
-
DFS(G)
- for each vertex u ∈ G.V
- u.color = WHITE
- u.π = NIL
- time = 0
- for each vertex u ∈ G.V
- if u.color = WHITE
- DFS-VISIT(G, u)
- ++time
- u.d = time
- u.color = GRAY
- for each v ∈ G.Adj(u)
- if v.color = WHITE
- v.π = u
- DFS-VISIT(G,v)
- u.color = BLACK
- ++time
- u.f = time
- Trace with
- Forget that, try something new
- Find graphviz online
-
digraph G { A [label=<A <br/> 0/0>, style="filled", color="lightblue"] B [label=<B <br/> 0/0>, style="filled", color="lightblue"] C [label=<C <br/> 0/0>, style="filled", color="lightblue"] D [label=<D <br/> 0/0>, style="filled", color="lightblue"] E [label=<E <br/> 0/0>, style="filled", color="lightblue"] F [label=<F <br/> 0/0>, style="filled", color="lightblue"] G [label=<G <br/> 0/0>, style="filled", color="lightblue"] H [label=<H <br/> 0/0>, style="filled", color="lightblue"] TIME [label=<TIME: 0 >, shape="box"] A->B A->C B->C A->D D->C C->E E->A D->F F->C G->D G->H H->C G->F //B->A [color="red"] }
- This is Θ(|V| + |E|), often written Θ(V + E)
- Some observations
- Ri = [u.d, u.f]
- Consider u, v
- If u.d < v.d < v.f < u.f,
- then u is the parent of v in the DFS tree
- and v is a descend of u in the DFS tree.
- if v.d < u.d < u.f < v.end
- u is a descent of v, but not a direct descendant.
- If v.d < v.f < u.d < u.f
- A cross between trees.
- CLRS classifies edges as
- Tree edges are part of the DFS tree
- Back edges connect back to a previous part of the tree
- Forward edges connect a parent in the DFS tree to a child, but are not part of the DFS tree
- Cross edges all other edges: everything else
- Between nodes in the DFS tree that have no relation.
- Between different DFS trees
- When we encounter a vertex we can classify the edges
- A White vertex indicates a tree edge
- A Gray vertex indicates a back edge
- A Black vertex indicates a forward or cross edge.
- A Directed Acyclic Graph (DAG) is a very used structure in CS.
- DFS can be used to determine if a graph is a dag or not, no back or cross edges.
- OR: if a DFS yields a back edge, the graph has a cycle.