Week 1 of Coursera's Algorithms on Graphs

1. Graph Basics.md

Graph Basics

Examples

• Internet: Webpages connected by links.
• Maps: Intersections connected by roads.
• Social Networks: People connected by friendships.
• Configuration Spaces: Possible configurations connected by motions.

Definition

Graph

An (undirected) Graph is a collection V of vertices, and a collection E of edges each of which connects a pair of vertices.

Loops and Multiple Edges

• Loops connect a vertex ot itself.
• Multiple edges between same vertices.
• If a graph has neither, it is simple.

Representing Graphs

Edge List

List of all edges

Adjacency Matrix

Matrix. Entries 1 if there is an edge, 0 if there is not.

Adjacency List

For each vertex, a list of adjacent vertices.

Summary

Op.	Is Edge?	List Edge	List Nbrs.
Adj. Matrix	Θ(1)	Θ(|V|^2)	Θ(|V|)
Edge List	Θ(|E|)	Θ(|E|)	Θ(|E|)
Adj. List	Θ(deg)	Θ(|E|)	Θ(deg)

For many problems, want adjacency list.

Density and Runtimes

Algorithm Runtimes

Graph algorithm runtimes depend on |V| and |E|.

Density

Which is faster, O(|V|^(3/2) or O(|E|)? Depends on the density, namely how many edges you have in terms of the number of vertices.

Dense Graphs

In dense graphs |E| ≈ |V|^2.

Sparse Graphs

In sparse graphs |E| ≈ |V|.

2. Exploring Undirected Graphs.md

Exploring Graphs

Reachability

Input: Graph G and vertex s

Output: The collection of vertices v of G so that there is a path from s to v

Component(s)
    DiscoveredNodes ← {s}
    while there is an edge e leaving DiscoveredNodes that has not been explored:
        add vertex at other end of e to DiscoveredNodes
    return DiscoveredNodes

Explore

Given each vertex boolean visited(v).

Explore(v)
    visited(v) ← true
    for (v, w) ∈ E:
        if not visited(w):
            Explore(w)

Need adjacency list representation!

Theorem

If all vertices start unvisitied, Explore(v) marks as visitied exactly the vertices reachable from v.

Proof

• Only explores things reachable from v.
• w not marked as visited unless explored.
• If w explored, all neighbors explored.
• u reachable from v by path.
• Assume w futhest along path explored.
• Must explore next item.

DFS

Sometimes you want to find all vertices of G, not just those reachable from V.

DFS(G)
    for all v ∈ V :
        mark v unvisited
    for v ∈ V :
        if not visited(v):
            Explore(v)

Runtime

Total runtime:

• O(1) work per vertex.
• O(1) work per edge.
• Total O(|V|+|E|)

Connectivity

Connected Components

Theorem

The vertices of a graph G can be partitioned into Connected Components so that v is reachable from w if and only if they are in the same connected component.

Algorithm

Input: Graph G

Output: The connected components of G

Idea:

• Explore(v) finds the connected component of v. Just need to repeat to find other components.
• Modify DFS to do this.
• Modify goal to label connected components.

Explore(v)
    visited(v) ← true
    CCnum(v) ← cc
    for (v, w) ∈ E:
        if not visited(w):
            Explore(w)

DFS(G)
    for all v ∈ V :
        mark v unvisited
    cc ← 1
    for v ∈ V :
        if not visited(v):
            Explore(v)
            cc ← cc + 1

Runtime: still O(|V|+|E|)

Previsit and Postvisit Orders

Previsit and Postvisit Functions

Explore(v)
    visited(v) ← true
    previsit(v)
    for (v, w) ∈ E:
        if not visited(w):
            Explore(w)
    postvisit(v)

Clock:

• Clock Keep track of order of visits.
• Clock ticks at each pre-/post- visit.
• Records previsit and postvisit times for each v.

Initialize clock to 1.

previsit(v)
    pre(v) ← clock
    clock ← clock + 1

postvisit(v)
    post(v) ← clock
    clock ← clock + 1

Lemma

For any vertices u, v the intervals [pre(u), post(u)] and [pre(v), post(v)] are either nested or disjoint.