Graph Algorithms

Bart Massey

---

Fundamentals Of Graphs

• "Graph" is a terrible name

• Graph G = (V, E) where

  • V is a set of vertices
  • E is a set of edges
    • Edge is an element of V x V
    • Implicit or explicit self-edges (v, v)?

• Basic kinds of graphs:

  • Directed: left vertex of edge is "in", right is "out"
  • Undirected: can ignore vertex orientation, or double edges

Graph Representations

• Edge List: vertices are implicit unless isolated

• Adjacency "List": adj: V -> set of V

• Adjacency Matrix: matrix of Bool indexed by in, out vertex

  • Edge List -> Adjacency Matrix
  • O(|E|) using self-initializing matrix

• Characteristic Function: on edges

Interesting Classes of Graph

• Connected: sequence of edges connecting every pair of points

  • Strongly connected: sequence of properly-oriented edges connecting every pair of points

• Planar: can be drawn without crossing edges

• Tree: connected, with |E| = |V| - 1

  • Usually rooted by some distinguished v in V

• Directed Acyclic Graph (DAG): Think of it as a directed tree with extra "downward" edges

Number Of Edges In Connected Graph

• |E| <= |V| (|V| - 1) / 2 [clique]
• |E| >= (|V| - 1) [line or tree]

Paths In Graphs

• A path on a graph (V, E) is a sequence p = (v[1], v[2] .. v[n]) of vertices such that

  forall i in {1..p.n-1} (p.v[i], p.v[i + 1]) is in E

• For a directed graph, this means that the path must go in the "right direction"

Determining Whether G is Strongly Connected

PROBLEM: STRONGLY CONNECTED?

Instance: A graph G = (V,E)

Question: Is G strongly connected, that is,

forall v1, v2 in V
    exists a path (v1..v2) in G

• Obvious algorithm

  forall v1 in V forall v2 in V if not check-for-path(v1, v2) return false return true

Checking For a Path Using Depth-First Search

check-for-path(v1, v2):
    if v1 == v2
        return true
    mark v1
    for v in neighbors(v1)
        if not marked(v) and check-for-path(v, v2)
            return true
    return false

• Worst case O(|E|) steps, O(|V|) space for recursion stack

Proving DFS Correct

• Prove that the algorithm returns true whenever the vertices are connected

  • By induction on shortest path-length |p| from v1 to v2
  • Base Case: If |p| = 0, the algorithm returns true
  • Inductive Case: If v is marked, then v would be visited a second time, so is not on a shortest path. Otherwise, by the inductive hypothesis, v1 + path(v..v2) must be a shortest path from v1 to v2.

• Prove that when the algorithm returns false, the vertices are not connected

  • By induction on shortest path-length |p| from v1 to v2
  • Base Case: If |p| = 0, the algorithm returns true
  • Base Case: Have that v1 <> v2 and that for every unmarked neighbor v either
    • v is marked, meaning that there is no shorter path from v1 to v2 through v
    • path(v..v2) does not exist, by inductive hypothesis

Checking For a Path Using Breadth-First Search

check-for-path(v1, v2):
    q <- new queue containing v1
    while q is not empty
        v <- extract q
        if v == v2
            return true
        mark v
        for v' in neighbors(v)
            if not marked(v')
                enqueue v' in queue
    return false

• Worst case O(|E|) steps, O(|V|) space for queue

Efficiency Of Naive Strong Connection Check

forall v1 in V
    forall v2 in V
         if not check-for-path(v1, v2)
             return false
return true

• Outer loops execute check-for-path O(|V|^2) times, and check-for-path is O(|E|), so O(|V|^2|E|) which is worst-case O(|V|^4)

Better Strong Connection Check

• Can get by with just one DFS!

  DFS(v1):
      mark v1
      for v in neighbors(v1)
          if not marked(v)
              DFS(v)
  
  check-strong-connected:
      DFS(v[1])
      for v in V
          if not marked(v)
              return false
      return true
  

• O(|E|)!