Note
This lecture is the last lecture in scope for Spring 2021 midterm 2.
CS61B, 2021
Lecture 22: Graphs II: Graph Traversal Implementations
Tree and Graph Traversals
Just as there are many tree traversals:
A
C
B
D
E
F
G
1
2
3
4
5
6
7
8
0
s
So too are there many graph traversals, given some source:
Shortest Paths Challenge
Goal: Given the graph above, find the shortest path from s to all other vertices.
0
1
2
3
4
5
6
7
s
BFS Answer
Breadth First Search.
Demo: Breadth First Paths
A queue is the opposite of a stack. Stack has push (addFirst) and pop (removeFirst).
Do this if you want to track distance value.
One use of BFS: Kevin Bacon
Graph with two types of vertices:
Perform BFS from s=Kevin Bacon.
BreadthFirstSearch for Google Maps
Would breadth first search be a good algorithm for a navigation tool (e.g. Google Maps)?
BreadthFirstSearch for Google Maps
Would breadth first search be a good algorithm for a navigation tool (e.g. Google Maps)?
Some roads are longer than others.
Will discuss how to deal with this in the next lecture.
Graph API
Graph Representations
To Implement our graph algorithms like BreadthFirstPaths and DepthFirstPaths, we need:
Our choices can have profound implications on:
�
Graph API Decision #1: Integer Vertices
Common convention: Number nodes irrespective of “label”, and use number throughout the graph implementation. To lookup a vertex by label, you’d need to use a Map<Label, Integer>.
Austin
Dallas
Houston
0
1
2
Intended graph.
How you’d build it.
Map<String, Integer>:
Austin: 0
Dallas: 1
Houston: 2
Graph API
The Graph API from our optional textbook.
Some features:
public class Graph {
public Graph(int V): Create empty graph with v vertices
public void addEdge(int v, int w): add an edge v-w
Iterable<Integer> adj(int v): vertices adjacent to v
int V(): number of vertices
int E(): number of edges
...
Graph API
The Graph API from our optional textbook.
Example client:
public class Graph {
public Graph(int V): Create empty graph with v vertices
public void addEdge(int v, int w): add an edge v-w
Iterable<Integer> adj(int v): vertices adjacent to v
int V(): number of vertices
int E(): number of edges
...
/** degree of vertex v in graph G */
public static int degree(Graph G, int v) {
int degree = 0;
for (int w : G.adj(v)) {
degree += 1;
}
return degree; }
(degree = # edges)
degree(G, 1) = 2
0
2
1
3
Graph API
The Graph API from our optional textbook.
Challenge: Try to write a client method called print that prints out a graph.
public class Graph {
public Graph(int V): Create empty graph with v vertices
public void addEdge(int v, int w): add an edge v-w
Iterable<Integer> adj(int v): vertices adjacent to v
int V(): number of vertices
int E(): number of edges
...
0
2
1
3
$ java printDemo
1 - 2
1 - 4
2 - 1
2 - 3
3 - 2
4 - 1
public static void print(Graph G) {
???
}
Graph API
The Graph API from our optional textbook.
Print client:
public class Graph {
public Graph(int V): Create empty graph with v vertices
public void addEdge(int v, int w): add an edge v-w
Iterable<Integer> adj(int v): vertices adjacent to v
int V(): number of vertices
int E(): number of edges
...
public static void print(Graph G) {
for (int v = 0; v < G.V(); v += 1) {
for (int w : G.adj(v)) {
System.out.println(v + “-” + w);
}
}
}
0
2
1
3
$ java printDemo
0 - 1
0 - 3
1 - 0
1 - 2
2 - 1
3 - 0
Graph API and DepthFirstPaths
Our choice of Graph API has deep implications on the implementation of DepthFirstPaths, BreadthFirstPaths, print, and other graph “clients”.
Graph Representation and Graph Algorithm Runtimes
Graph Representations
To Implement our graph algorithms like BreadthFirstPaths and DepthFirstPaths, we need:
Our choices can have profound implications on:
�
Graph Representations
Just as we saw with trees, there are many possible implementations we could choose for our graphs.
Let’s review briefly some representations we saw for trees.
Tree Representations
We’ve seen many ways to represent the same tree. Example: 1a.
w
x
y
z
1a: Fixed Number of Links (One Per Child)
w
z
x
y
Tree Representations
We’ve seen many ways to represent the same tree. Example: 3.
w
z
x
y
w
x
y
z
Key[] keys
3: Array of Keys
Uses much less memory and operations will tend to be faster.
… but only works for complete trees.
Graph Representations
0
1
2
Graph Representation 1: Adjacency Matrix.
| 0 | 1 | 2 |
0 | 0 | 1 | 1 |
1 | 0 | 0 | 1 |
2 | 0 | 0 | 0 |
0
1
3
2
| 0 | 1 | 2 | 3 |
0 | 0 | 1 | 0 | 0 |
1 | 1 | 0 | 1 | 0 |
2 | 0 | 1 | 0 | 1 |
3 | 0 | 0 | 1 | 0 |
For undirected graph: Each edge is represented twice in the matrix. Simplicity at the expense of space.
s
t
v
w
Graph Representations
Graph Representation 1: Adjacency Matrix.
0
1
3
2
| 0 | 1 | 2 | 3 |
0 | 0 | 1 | 0 | 0 |
1 | 1 | 0 | 1 | 0 |
2 | 0 | 1 | 0 | 1 |
3 | 0 | 0 | 1 | 0 |
v
w
G.adj(2) returns an iterator that will ultimately provide 1, then 3.
Graph Printing Runtime: http://yellkey.com/allow
What is the order of growth of the running time of the print client from before if the graph uses an adjacency-matrix representation, where V is the number of vertices, and E is the total number of edges?
Runtime to iterate over v’s neighbors?
How many vertices do we consider?
| 0 | 1 | 2 | 3 |
0 | 0 | 1 | 0 | 0 |
1 | 1 | 0 | 1 | 0 |
2 | 0 | 1 | 0 | 1 |
3 | 0 | 0 | 1 | 0 |
0
1
3
2
for (int v = 0; v < G.V(); v += 1) {
for (int w : G.adj(v)) {
System.out.println(v + “-” + w);
}
}
Graph Printing Runtime: http://yellkey.com/allow
What is the order of growth of the running time of the print client from before if the graph uses an adjacency-matrix representation, where V is the number of vertices, and E is the total number of edges?
Runtime to iterate over v’s neighbors?
How many vertices do we consider?
| 0 | 1 | 2 | 3 |
0 | 0 | 1 | 0 | 0 |
1 | 1 | 0 | 1 | 0 |
2 | 0 | 1 | 0 | 1 |
3 | 0 | 0 | 1 | 0 |
0
1
3
2
for (int v = 0; v < G.V(); v += 1) {
for (int w : G.adj(v)) {
System.out.println(v + “-” + w);
}
}
More Graph Representations
Representation 2: Edge Sets: Collection of all edges.
0
1
2
{(0, 1), (0, 2), (1, 2)}
More Graph Representations
Representation 3: Adjacency lists.
0
1
2
0
1
2
[1, 2]
[2]
Graph Printing Runtime: http://yellkey.com/just
What is the order of growth of the running time of the print client if the graph uses an adjacency-list representation, where V is the number of vertices, and E is the total number of edges?
Runtime to iterate over v’s neighbors?
How many vertices do we consider?
a
b
c
0
1
2
[1, 2]
[2]
for (int v = 0; v < G.V(); v += 1) {
for (int w : G.adj(v)) {
System.out.println(v + “-” + w);
}
}
Graph Printing Runtime: http://yellkey.com/just
What is the order of growth of the running time of the print client if the graph uses an adjacency-list representation, where V is the number of vertices, and E is the total number of edges?
Runtime to iterate over v’s neighbors? List can be between 1 and V items.
How many vertices do we consider?
a
b
c
0
1
2
[1, 2]
[2]
Best case: Θ(V) Worst case: Θ(V2)
for (int v = 0; v < G.V(); v += 1) {
for (int w : G.adj(v)) {
System.out.println(v + “-” + w);
}
}
Graph Printing Runtime: http://yellkey.com/effort
What is the order of growth of the running time of the print client if the graph uses an adjacency-list representation, where V is the number of vertices, and E is the total number of edges?
Runtime to iterate over v’s neighbors? List can be between 0 and V items.
How many vertices do we consider?
a
b
c
0
1
2
[1, 2]
[2]
Best case: Θ(V) Worst case: Θ(V2)
?
?
?
?
?
for (int v = 0; v < G.V(); v += 1) {
for (int w : G.adj(v)) {
System.out.println(v + “-” + w);
}
}
Graph Printing Runtime: http://yellkey.com/effort
What is the order of growth of the running time of the print client if the graph uses an adjacency-list representation, where V is the number of vertices, and E is the total number of edges?
�Best case: Θ(V) Worst case: Θ(V2)
All cases: Θ(V + E)
a
b
c
0
1
2
[1, 2]
[2]
for (int v = 0; v < G.V(); v += 1) {
for (int w : G.adj(v)) {
System.out.println(v + “-” + w);
}
}
Graph Printing Runtime
Runtime: Θ(V + E)
How to interpret: No matter what “shape” of increasingly complex graphs we generate, as V and E grow, the runtime will always grow exactly as Θ(V + E).
V is total number of vertices.
E is total number of edges in the entire graph.
for (int v = 0; v < G.V(); v += 1) {
for (int w : G.adj(v)) {
System.out.println(v + “-” + w);
}
}
Graph Representations
Runtime of some basic operations for each representation:
In practice, adjacency lists are most common.
idea | addEdge(s, t) | for(w : adj(v)) | print() | hasEdge(s, t) | space used |
adjacency matrix | Θ(1) | Θ(V) | Θ(V2) | Θ(1) | Θ(V2) |
list of edges | Θ(1) | Θ(E) | Θ(E) | Θ(E) | Θ(E) |
adjacency list | Θ(1) | Θ(1) to Θ(V) | Θ(V+E) | Θ(degree(v)) | Θ(E+V) |
Note: These operations are not part of the Graph class’s API.
Bare-Bones Undirected Graph Implementation
Cannot create array of anything involving generics, so have to use weird cast as with project 1A.
public class Graph {
private final int V; private List<Integer>[] adj;
public Graph(int V) {
this.V = V;
adj = (List<Integer>[]) new ArrayList[V];
for (int v = 0; v < V; v++) {
adj[v] = new ArrayList<Integer>();
}
}
public void addEdge(int v, int w) {
adj[v].add(w); adj[w].add(v);
}
public Iterable<Integer> adj(int v) {
return adj[v];
}
}
Graph Traversal Implementations and Runtime
Depth First Search Implementation
Common design pattern in graph algorithms: Decouple type from processing algorithm.
public class Paths {
public Paths(Graph G, int s): Find all paths from G
boolean hasPathTo(int v): is there a path from s to v?
Iterable<Integer> pathTo(int v): path from s to v (if any)
}
Paths.java
Example Usage
Start by calling: Paths P = new Paths(G, 0);
Paths.java
public class Paths {
public Paths(Graph G, int s): Find all paths from G
boolean hasPathTo(int v): is there a path from s to v?
Iterable<Integer> pathTo(int v): path from s to v (if any)
}
DepthFirstPaths
DepthFirstPaths, Recursive Implementation
public class DepthFirstPaths {
private boolean[] marked;
private int[] edgeTo;
private int s;
public DepthFirstPaths(Graph G, int s) {
...
dfs(G, s);
}
private void dfs(Graph G, int v) {
marked[v] = true;
for (int w : G.adj(v)) {
if (!marked[w]) {
edgeTo[w] = v;
dfs(G, w);
}
}
}
...
}
marked[v] is true iff v connected to s
edgeTo[v] is previous vertex on path from s to v
find vertices connected to s.
not shown: data structure initialization
recursive routine does the work and stores results in an easy to query manner!
Question to ponder: How would we write pathTo(v) and hasPathTo(v)?
DepthFirstPaths, Recursive Implementation
public class DepthFirstPaths {
private boolean[] marked;
private int[] edgeTo;
private int s;
...
public Iterable<Integer> pathTo(int v) {
if (!hasPathTo(v)) return null;
List<Integer> path = new ArrayList<>();
for (int x = v; x != s; x = edgeTo[x]) {
path.add(x);
}
path.add(s);
Collections.reverse(path);
return path;
}
public boolean hasPathTo(int v) {
return marked[v];
}
}
marked[v] is true iff v connected to s
edgeTo[v] is previous vertex on path from s to v
Runtime for DepthFirstPaths
Give a O bound for the runtime for the DepthFirstPaths constructor.
Assume graph uses adjacency list!
public class DepthFirstPaths {
private boolean[] marked;
private int[] edgeTo;
private int s;
public DepthFirstPaths(Graph G, int s) {
...
dfs(G, s);
}
private void dfs(Graph G, int v) {
marked[v] = true;
for (int w : G.adj(v)) {
if (!marked[w]) {
edgeTo[w] = v;
dfs(G, w);
}
}
} ...
}
Runtime for DepthFirstPaths
Give a O bound for the runtime for the DepthFirstPaths constructor.
O(V + E)
Assume graph uses adjacency list!
public class DepthFirstPaths {
private boolean[] marked;
private int[] edgeTo;
private int s;
public DepthFirstPaths(Graph G, int s) {
...
dfs(G, s);
}
private void dfs(Graph G, int v) {
marked[v] = true;
for (int w : G.adj(v)) {
if (!marked[w]) {
edgeTo[w] = v;
dfs(G, w);
}
}
} ...
}
edge considerations, each constant time
(no more than 2E calls)
vertex visits (no more than V calls)
Cost model in analysis above is the sum of:
Various Cost Models for DFS
Four cost models for DFS:
We never formally defined asymptotics on multiple variables, and it turns out to be somewhat poorly defined.
Runtime for DepthFirstPaths
Very hard question: Could we say the runtime is O(E)?
Argument: Can only visit a vertex if there is an edge to it.
Assume graph uses adjacency list!
public class DepthFirstPaths {
private boolean[] marked;
private int[] edgeTo;
private int s;
public DepthFirstPaths(Graph G, int s) {
...
dfs(G, s);
}
private void dfs(Graph G, int v) {
marked[v] = true;
for (int w : G.adj(v)) {
if (!marked[w]) {
edgeTo[w] = v;
dfs(G, w);
}
}
} ...
}
Runtime for DepthFirstPaths
Very hard question: Could we say the runtime is O(E)? No.
Can’t say O(E)!
Our cost model earlier (dfs calls + marked checks) does not provide a tight bound.
Assume graph uses adjacency list!
public class DepthFirstPaths {
private boolean[] marked;
private int[] edgeTo;
private int s;
public DepthFirstPaths(Graph G, int s) {
...
dfs(G, s);
}
private void dfs(Graph G, int v) {
marked[v] = true;
for (int w : G.adj(v)) {
if (!marked[w]) {
edgeTo[w] = v;
dfs(G, w);
}
}
} ...
}
Graph Problems
Runtime is O(V+E)
Space is Θ(V).
Problem | Problem Description | Solution | Efficiency (adj. list) |
s-t paths | Find a path from s to every reachable vertex. | DepthFirstPaths.java Demo [update] | O(V+E) time Θ(V) space |
BreadthFirstPaths Implementation
marked[v] is true iff v connected to s
edgeTo[v] is previous vertex on path from s to v
set up starting vertex
for freshly dequeued vertex v, for each neighbor that is unmarked:
public class BreadthFirstPaths {
private boolean[] marked;
private int[] edgeTo;
...
private void bfs(Graph G, int s) {
Queue<Integer> fringe =
new Queue<Integer>();
fringe.enqueue(s);
marked[s] = true;
while (!fringe.isEmpty()) {
int v = fringe.dequeue();
for (int w : G.adj(v)) {
if (!marked[w]) {
fringe.enqueue(w);
marked[w] = true;
edgeTo[w] = v;
}
}
}
}
Graph Problems
Runtime for shortest paths is also O(V+E)
Space is Θ(V).
Problem | Problem Description | Solution | Efficiency (adj. list) |
s-t paths | Find a path from s to every reachable vertex. | DepthFirstPaths.java | O(V+E) time Θ(V) space |
s-t shortest paths | Find a shortest path from s to every reachable vertex. | BreadthFirstPaths.java | O(V+E) time Θ(V) space |
Layers of Abstraction
Clients and Our Graph API
Our choice of Graph API has deep implications on the implementation of DepthFirstPaths, BreadthFirstPaths, print, and other graph “clients”.
Our Graph API and Implementation
Our choice of how to implement the Graph API has profound implications on runtime.
Our Graph API and Implementation
Our choice of how to implement the Graph API has profound implications on runtime.
Runtime for DepthFirstPaths
Give a tight O bound for the runtime for the DepthFirstPaths constructor.
Assume graph uses adjacency matrix!
public class DepthFirstPaths {
private boolean[] marked;
private int[] edgeTo;
private int s;
public DepthFirstPaths(Graph G, int s) {
...
dfs(G, s);
}
private void dfs(Graph G, int v) {
marked[v] = true;
for (int w : G.adj(v)) {
if (!marked[w]) {
edgeTo[w] = v;
dfs(G, w);
}
}
} ...
}
Runtime for DepthFirstPaths
Give a tight O bound for the runtime for the DepthFirstPaths constructor.
O(V2)
Assume graph uses adjacency matrix!
public class DepthFirstPaths {
private boolean[] marked;
private int[] edgeTo;
private int s;
public DepthFirstPaths(Graph G, int s) {
...
dfs(G, s);
}
private void dfs(Graph G, int v) {
marked[v] = true;
for (int w : G.adj(v)) {
if (!marked[w]) {
edgeTo[w] = v;
dfs(G, w);
}
}
} ...
}
We create ≤ V iterators.
Essentially, iterating over the entire adjacency matrix takes O(V2) time.
Graph Problems for Adjacency Matrix Based Graphs
If we use an adjacency matrix, BFS and DFS become O(V2).
Problem | Problem Description | Solution | Efficiency (adj. matrix) |
s-t paths | Find a path from s to every reachable vertex. | DepthFirstPaths.java | O(V2) time Θ(V) space |
s-t shortest paths | Find a shortest path from s to every reachable vertex. | BreadthFirstPaths.java | O(V2) time Θ(V) space |
Summary
Summary
BFS: Uses a queue instead of recursion to track what work needs to be done.
Graph API: We used the Princeton algorithms book API today.
public class Graph {
public Graph(int V): Create empty graph with v vertices
public void addEdge(int v, int w): add an edge v-w
Iterable<Integer> adj(int v): vertices adjacent to v
int V(): number of vertices
int E(): number of edges ...
Summary
Graph Implementations: Saw three ways to implement our graph API.
Choice of implementation has big impact on runtime and memory usage!
Live Lecture Exercise
Switching Things Up
Breadth First Search.
Demo: Breadth First Paths
Do this if you want to track distance value.
Switching Things Up
??? First Search.
Try running ??? first search. Assume adjacency lists are in numerical order.
1
2
3
4
5
6
7
8
0
s
Stack:
??? First Search Visit Order: []
0
Try running ??? first search. Assume adjacency lists are in numerical order.
1
2
3
4
5
6
7
8
0
s
Stack:
??? First Search Visit Order: []
0
Try running ??? first search. Assume adjacency lists are in numerical order.
1
2
3
4
5
6
7
8
0
s
Stack:
??? First Search Visit Order: [0]
Try running ??? first search. Assume adjacency lists are in numerical order.
1
2
3
4
5
6
7
8
0
s
Stack:
??? First Search Visit Order: [0]
1
Try running ??? first search. Assume adjacency lists are in numerical order.
1
2
3
4
5
6
7
8
0
s
Stack:
??? First Search Visit Order: [0, 1]
Try running ??? first search. Assume adjacency lists are in numerical order.
1
2
3
4
5
6
7
8
0
s
Stack:
??? First Search Visit Order: [0, 1]
2
4
Try running ??? first search. Assume adjacency lists are in numerical order.
1
2
3
4
5
6
7
8
0
s
Stack:
??? First Search Visit Order:
[0, 1, 4]
2
3
5
Try running ??? first search. Assume adjacency lists are in numerical order.
1
2
3
4
5
6
7
8
0
s
Stack:
??? First Search Visit Order:
[0, 1, 4, 5]
2
3
Try running ??? first search. Assume adjacency lists are in numerical order.
1
2
3
4
5
6
7
8
0
s
Stack:
??? First Search Visit Order:
[0, 1, 4, 5]
2
3
6
8
Try running ??? first search. Assume adjacency lists are in numerical order.
1
2
3
4
5
6
7
8
0
s
Stack:
??? First Search Visit Order:
[0, 1, 4, 5, 8]
2
3
6
*
Try running ??? first search. Assume adjacency lists are in numerical order.
1
2
3
4
5
6
7
8
0
s
Stack:
??? First Search Visit Order:
[0, 1, 4, 5, 8, 6]
2
3
7
Try running ??? first search. Assume adjacency lists are in numerical order.
1
2
3
4
5
6
7
8
0
s
Stack:
??? First Search Visit Order:
[0, 1, 4, 5, 8, 6, 7]
2
3
Try running ??? first search. Assume adjacency lists are in numerical order.
1
2
3
4
5
6
7
8
0
s
Stack:
??? First Search Visit Order:
[0, 1, 4, 5, 8, 6, 7, 3]
2
Try running ??? first search. Assume adjacency lists are in numerical order.
1
2
3
4
5
6
7
8
0
s
Stack:
??? First Search Visit Order:
[0, 1, 4, 5, 8, 6, 7, 3, 2]
Try running ??? first search. Assume adjacency lists are in numerical order.
1
2
3
4
5
6
7
8
0
s
Stack:
??? First Search Visit Order:
[0, 1, 4, 5, 8, 6, 7, 3, 2]
DFS (Pre-order):
[0, 1, 2, 5, 4, 3, 6, 7, 8]
Try running R???R first search, which uses reverse order of adjacency lists.
1
2
3
4
5
6
7
8
0
s
Stack:
??? First Search Visit Order:
[0, 1, 4, 5, 8, 6, 7, 3, 2]
DFS (Pre-order):
[0, 1, 2, 5, 4, 3, 6, 7, 8]
R???R First Search Visit Order:
[0, 1, 2, 5, 6 RRRHRHH (buzzer sound)]
Interesting fact:
In 61C, you’ll learn how recursive calls are implemented at a low level using a stack, i.e. in REAL recursive code, there is an explicit stack being utilized (but below the level of abstraction that you usually think about).�