For an intro to graphs refer to this page for more details.

Exploring Undirected Graph

Let $G = (V, E)$ be an undirected graph.

Task: Find all vertices that can be reached from a given vertex $v \in V$.

def explore(v):
    visited(v) = True
    previsit(v) # see later
    for each edge {u,v} in E do:
        if visited(u) = False:
            call explore(u)
    postvisit(v) # see later

The number of vertices u such that “visited(u) = false” decreases in each recursive call. Since there is a finite number of vertices, the algorithm eventually terminates.

Lemma

Assume that, initially, visited(u) = False. After explore(v) has terminated, visited(u) = True $\iff$ there is a path from $v$ to $u$.

Connected Components of G = (V, E)

def DFS (G):
  for all v in V do:
    visited (v) = false
  cc = 0
  for all v in V do:
    if visited (v) = false:
      cc = cc + 1
      explore (v)

Run-time of DFS

First for-loop: $O(|V|)$ time

Second for-loop:

• explore(u) is called exactly once for each vertex u (this may be a recursive call)
• time spent for explore(u), excluding recursive calls is $O(1 + degree(u))$

Total time: $O (|V| + \sum_{u \in V}(1+ \mathrm{degree}(u))) = O(|V| + |V| + 2|E|) = O(|V| + |E|)$

Directed Graphs

Assume that $G = (V,E)$ is directed and acyclic.

Topological Sorting or Ordering is the numbering the vertices $1, 2, ... , n$ such that for each edge $(u,v), (u) < (v)$

def TopologicalOrdering(G):
  # Input: a directed acyclic graph G (V, E)
  # Output: A topological ordering of V
  k = 1
  while V != {} do:
    Choose a vertex u in V with indegree 0
    Give u the number k
    k = k + 1
    Remove u from G

Prenumbers and Postnumbers

Let $G = (V, E)$ be a directed graph. For each vertex $v \in V$, we define the following two numbers with respect to Depth-First-Search.

• pre(v): the first time we visit $v$ (the time at which explore(v) is called)
• post(v): the time at which explore(v) is finished.

Use variable clock. At start, clock = 1.

def previsit(v):
  pre(v) = clock
  clock += 1
def postvisit(v):
  post(v) = clock
  clock += 1

4 Types of Edges

Tree edge

• edge $v \rightarrow u$
• $explore(u)$ is called as a recursive call within $explore(v)$
• solid edge
• literally the edges we follow when we execute DFS

Forward edge

• edge $v \rightarrow u$ where in the (solid) tree,
• $u$ is in subtree of $v$
• $u$ is not a child of $v$
• shortcut that brings you down the tree

Back edge

• edge $v \rightarrow u$ where in the (solid) tree,
• $v$ in subtree of $u$
• enable you to go back in the tree

Cross edge

• lets you go from one subtree to another
• all other edges

Acyclic vs Cyclic

$G$ has a directed cycle if and only if DFS-forest has a back-edge.

How to test if a directed graph is cyclic?

1. Run DFS (including pre/post-numbers)
2. For each non-tree edge(v, u), test if pre(u) < pre(v) > post(v) < post(u)

• if "yes" fpr at least one non-tree edge, return "cyclic"
• if "no" for all non-tree edges, return "acyclic"

Running time: O(|V| + |E|)

Topological Sort for directed acyclic graph

1. Run DFS (including pre/post-numbers)
2. Run Bucket Sort to sort the vertices by post-number.
3. Obtain the topological ordering from the reverse sorted order of the post-numbers.

Shortest Paths

Dijkstra's Algorithm

Input:

• A directed graph $G = (V, E)$ where each edge $(u,v) \in E$ has a weight $wt (u,v) > 0$
• A vertex $s \in V$ called the source

Output:

• For each vertex $v \in V$, $(s,v)$ = length of a shortest path from $s$ to $v$.

For each vertex $v ∈ V$, maintain variable $d(v)$ = length of a shortest path from $s$ to $v$ found so far.

At start, $d(v) = 0$ if $v = s, \infty$ if $v \neq s$

Loop: Pick a vertex u for which $d(u) = δ(s, u)$. For each edge $(u, v), d(v) = min {d(v), d(u) + wt(u, v)}$

for each vertex v in V:
  d(v) = infinity
d(s) = 0
S = {}
Q = V
while Q != {}:
  u = vertex in Q for which d(u) is minimum
  delete u from Q
  insert u into S
  for each edge (u,v):
    d(v) = min (d(v), d(u) + wt(u,v))

Example:

1. Let $n = |V|$ and $m = |E|$.
2. Store $Q$ in a min-heap, where the key of each vertex is $d(v)$.
3. Initialization: $O(n)$ (including the time to build the heap storing $Q=V$).
4. One iteration:

• Find $u$ and delete it from Q.
  • extract_min: $O(log (n))$ time.
• For each edge (u, v), we update $d(v)$
  • decrease_key: $O (log (n))$ time.

Total time for one iteration: $O(log(n)) + O(\mathrm{outdegree}(u) · log(n))$
Total running time: $O (n) + O (\sum_{u \in V} (O(log(n)) + O(\mathrm{outdegree}(u) · log(n)))) = O(n) + O (log(n)(n + 2m)) = O ((m + n) log(n))$

Dijkstra Correctness

Theorem

Let $G = (V, E)$ be a weighted directed graph and $s \in V$ be a source vertex. Dijkstra algorithm finds the lengths of the shortest paths from $s$ to all vertices in $V$.

We prove by induction that

1. if a vertex $u$ is in $S$, then $d(u)$ gives the length of a shortest path from $s$ to $u$ and
2. if a vertex $u$ is not in $S$, then $d(u)$ gives the length of a shortest special path from $s$ to $u$.

Base case:

1. At the beginning, $S = {}$, so (1) above is vacuously true.
2. Since $S = {}$, the other vertices simply cannot be reached by following a special path from $s$. Since $d$ is initialized to $\infty$, then (2) above also holds when the algorithm starts.

Induction hypothesis: Assume that both (1) and (2) hold right before we add a new vertex v to S. We address induction steps (1) and (2) separately.

Induction step (1): By the induction hypothesis (1), before the addition of $v$, we already know a shortest path from $s$ to all vertices that are in $S$. Adding $v$ to $S$ does not change these shortest paths.

As for node $v$, it is about to be inserted in $S$. Before adding it to $S$, we must check $d(v)$ gives the length of a shortest path from $s$ to $v$.

So we compare $d(v)$ to the lengths of all paths from $s$ to $v$. There are two kinds of paths:

• the paths that are special
• the ones that are not

By the induction hypothesis (2), we already know that $d(v)$ is less than or equal to the length of any special path from $s$ to $v$. A non-special path from $s$ to $v$ is one which contains at least one vertex $x \neq v$ that is not in $S$. But such a path has length at least $d(x) \geq d(v)$.

Hence, $d(v)$ is less than or equal to the length of any path from $s$ to $v$, which means that $d(v)$ gives the length of a shortest path from $s$ to $v$. So the induction step is complete for $(1)$.

Induction step (2): Consider a node $w \neq v$ which is not in $S$. Let $y$ be the last vertex in $S$ encountered on a shortest special path from $s$ to $w$. We consider:

• $y \neq v$
• $y = v$

If $y \neq v$ then adding $v$ to $S$ does not change the value of $d(w)$. Hence, by the induction hypothesis (2), $d(w)$ gives the length of a shortest special path from $s$ to $w$.

If $y = v$, then by doing $d(w) = \mathrm{min} (d(w), d(v) + wt(v, w))$, we ensure that after adding $v$ to $S$, $d(w)$ gives the length of a shortest special path from $s$ to $w$.