Suggest edit — depth first search

Title

Name

Note

---
title: "depth first search"
type: concept
related: [Topological Sort]
source: https://www.jemoka.com/posts/kbhdepth_first_search/
confidence: high
status: active
---

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&rsquo;}^{} O\qty(\text{deg}\qty(w)) + O\qty(1) = O\qty(|E|+|V|) = O\qty(n+m)\)
use cases topological sort see topological sort