2024-03-03

Sunday, March 3rd, 2024

Share your smile with the world. It's a symbol of friendship and peace.

— Christie Brinkley

ECS122A Lecture Notes: DFS

Depth-first Search (DFS)

• depth-first search
• input: a graph
• output:
  • discovery and finish times of each vertex
  • classification of edges
• vertex color
  • white: undiscovered
  • gray: discovered; has not finished processing
  • black: processing finished (all neighbors visited)
• edge classification during DFS
  • T (tree edge): encountered new vertex (edge from gray to white)
  • B (back edge): descendant to ancestor (edge from gray to gray)
  • F (forward edge): ancestor to descendant (edge from gray to black)
  • C (cross edge): any other edges (from trees to subtrees) (edge from gray to black)
  • Classify by the first type that matches, since it undirected graphs there can be ambiguity, e.g. $(u,v)=(v,u)$
• recursive procedure
  • DFS
    • Set all vertices’ color to white
    • For each vertex in graph (this is needed because we cannot assume the graph is connected)
      • Visit the vertex if it’s white
  • DFS Visit
    • Mark the vertex as gray
    • Increment time. Save the discovery time
    • Visit each neighboring white vertex
    • Increment time. Save the finish time.
• in-progress vertices (gray) can be processed in a stack (as opposed to BFS where vertices are processed in a queue)
  • push the node onto the stack when first encountered
  • when visiting the node, pop it, push all of its white neighbors onto the stack, then push the node again to save the finish time later
• runtime: $\Theta (|V|+|E|)$
  • tight bound, since the algorithm is guaranteed to explore all vertices and all edges

Shortest path finding

• single-source shortest path (SSSP) problem: given a source vertex in a weighted graph, for each vertex, find the path to this vertex with the minimum weight
• Bellman-Ford algorithm
  • basic algorithm for path finding
  • can handle negative edge weights
  • input:
    • set of vertices $V$ and edges $E$
    • weights of each edge
    • source vertex $s$
  • output:
    • $d[v]=\delta (s,v)$: weight of the shortest path from source $s$ to $v$
    • $\pi [v]$: parent (predecessor) of $v$ (can be used to traceback the shortest path)
    • returns true if source $s$ won’t reach any negative-weight cycles, false otherwise
  • procedure
    • initialize $d[v]=\infty$ and $\pi [v]=\mathrm{nil}$ for each vertex $v$
    • $d[s]=0$
    • iterate $|V|-1$ times
      • for each edge $(u,v)\in E$
        • if $d[v]>d[u]+w(u,v)$ (if $s-\cdots -v$ has a shorter path through $s-\cdots -u-v$, relax)
          • $d[v]=d[u]+w(u,v)$
          • $\pi [v]=u$
    • for each edge $(u,v)\in E$
      • if $d[v]>d[u]+w(u,v)$
        • return false (negative weight cycle found)
    • return true
  • runtime: $\Theta (|V|\cdot |E|)$
• Dijkstra’s algorithm
  • traits
    • does not handle edges with negative weight
    • BFS-like. Can just use BFS if all edges have the same weight (1).
    • uses $Q$, a priority queue keyed by $d[v]$ (in contrast, BFS uses a FIFO queue)
  • input
    • set of edges $E$ and vertices $V$
    • $w(u,v)$: weight of edge from $u$ to $v$
    • source vertex $s$
  • output
    • $d[v]$: shortest path distance from $s$ to $v$
    • $\pi [v]$: predecessor of $v$ (traceback)
  • procedure (with min priority queue)
    • initialize $d[v]=\infty$ and $\pi [v]=\mathrm{nil}$ for each vertex $v$
    • $d[s]=0$
    • $Q=V$ (initialize min priority queue keyed by $d[v]$)
    • while queue is not empty
      • $u$ = q.pop() – pop vertex with smallest shortest path weight
      • for each edge $(u,v)\in E$, try to update $v$‘s shortest path weight:
        • if $d[v]>d[u]+w(u,v)$
          • $s-\cdots -v$ path through neighbor $u$ has lower weight, update distance and predecessor
          • $d[v]=d[u]+w(u,v)$
          • $\pi [v]=u$
    • return $d$, $\pi$
  • runtime
    • $O(|E|\lg |V|)$ with min priority queue
    • $O(V^2)$ without priority queue
  • Dijkstra’s algorithm is greedy (similar to BFS & MFS algorithms, as it replaces the current known path from $s$ to $v$ if a path through $u$ proves to be shorter.
• DAG single-source shortest path (SSSP) algorithm
  • A DAG can have negative weight edges, but by definition won’t have negative weight cycle (or any cycle for that matter)
  • runtime: $O(|V|+|E|)$, a significant upgrade from Bellman-Ford algorithm
  • procedure
    • topologically sort vertices of $G=(V,E)$
    • initialize $d[v]=\infty$ and $\pi [v]=\mathrm{nil}$ for each vertex $v=V$
    • $d[s]=0$
    • for each $u=V$ taken in topological order
      • for each adjacent vertex $v$
        • if $d[v]>d[u]+w(u,v)$
          • $d[v]=d[u]+w(u,v)$
          • $\pi [v]=u$
    • return $d$, $\pi$