Each vertex keeps track of three states: visited, in progress, done. We also keep track of when we going to enter it and when we are also be done

# initialize vertex.state = UNVISITED across graph

def dfs(vertex, currentTime):
    vertex.startTime = currentTime
    currentTime++

    vertex.state = IN_PROGRESS

    for v in vertex.neightbors:
        if v.state == UNVISITED: # to prevent loops
            currentTime = dfs(v, currentTime)
            currentTime += 1
    w.finishTime = currentTime
    w.state == DONE

    return currentTime

This explores all connected component starting from each vertex, so presumably you have to repeatedly by iterating through all verticies.

runtime

• visit vertex in \(G\) exactly once
• at each vertex \(w\), we
  • do \(O\qty(1)\) bookkeeping
  • loop over \(w\) neighbors (one per neighbor) and recurse \(O\qty(\text{deg}\qty(w))\)

This gives \(\sum_{w \in V’}^{} O\qty(\text{deg}\qty(w)) + O\qty(1) = O\qty(|E|+|V|) = O\qty(n+m)\)

use cases

topological sort

see topological sort