# 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 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|)!