## Graphs

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