BFS, DFS and Implementations
1
Lecture 23 (Graphs 2)
CS61B, Fall 2023 @ UC Berkeley
Slides credit: Josh Hug
Princeton Graphs API
Lecture 23, CS61B, Fall 2023
The All Paths Problem
The All Shortest Paths Problem
Graph Implementations and Runtime
Project 2B Note
Graph Representations
To Implement a graph algorithm like DepthFirstPaths, we need:
Our choices can have profound implications on:
�
Set
TreeSet
HashSet
Graph
??
??
API
Concrete
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 Princeton’s algorithms 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
0 - 1
0 - 3
1 - 0
1 - 2
2 - 1
3 - 0
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”.
DepthFirstPaths Implementation
Lecture 23, CS61B, Fall 2023
The All Paths Problem
The All Shortest Paths Problem
Graph Implementations and Runtime
Project 2B Note
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
Let’s review DepthFirstPaths by running the demo from last lecture again.
Will then discuss:
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
To analyze the runtime, we need to create a concrete Graph Implementation.
The Adjacency List
Lecture 23, CS61B, Fall 2023
The All Paths Problem
The All Shortest Paths Problem
Graph Implementations and Runtime
Project 2B Note
Graph Representations
To Implement our graph algorithms like BreadthFirstPaths and DepthFirstPaths, we need:
Our choices can have profound implications on:
�
Graph
??
??
API
Concrete
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
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 Representations
To Implement our graph algorithms like BreadthFirstPaths and DepthFirstPaths, we need:
Our choices can have profound implications on:
�
Graph
??
Adjacency List
API
Concrete
Graph Printing Runtime: http://yellkey.com/second
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/second
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]
for (int v = 0; v < G.V(); v += 1) {
for (int w : G.adj(v)) {
System.out.println(v + “-” + w);
}
}
Best case: Θ(V) Worst case: Θ(V2)
Graph Printing Runtime: http://yellkey.com/support
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]
for (int v = 0; v < G.V(); v += 1) {
for (int w : G.adj(v)) {
System.out.println(v + “-” + w);
}
}
Best case: Θ(V) Worst case: Θ(V2)
?
?
?
?
?
Graph Printing Runtime: http://yellkey.com/support
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)
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);
}
}
Cost model in this analysis is the sum of:
Θ(V + E) Interpretation
Runtime: Θ(V + E)
How to interpret: No matter what “family” 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);
}
}
More Θ(V + E) Interpretation
Runtime: Θ(V + E)
Θ(V + E) is the equivalent of Θ(max(V, E)).
Note: We never formally defined asymptotics on multiple variables, and it turns out to be somewhat poorly defined.
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);
}
}
DepthFirstPaths Runtime
Lecture 23, CS61B, Fall 2023
The All Paths Problem
The All Shortest Paths Problem
Graph Implementations and Runtime
Project 2B Note
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:
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 | O(V+E) time Θ(V) space |
BreadthFirstPaths
Lecture 23, CS61B, Fall 2023
The All Paths Problem
The All Shortest Paths Problem
Graph Implementations and Runtime
Project 2B Note
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 (Video Viewers Only)
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.
A queue is the opposite of a stack. Stack has push (addFirst) and pop (removeFirst).
Do this if you want to track distance value.
BreadthFirstPaths Demo
Goal: Find shortest path between s and every other vertex.
1
2
3
4
5
6
7
8
0
s
# marked edgeTo distTo
0 F - 0
1 F - -
2 F - -
3 F - -
4 F - -
5 F - -
6 F - -
7 F - -
8 F - -
Queue: []
BreadthFirstPaths Demo
Goal: Find shortest path between s and every other vertex.
1
2
3
4
5
6
7
8
0
s
Queue: [0]
# marked edgeTo distTo
0 T - 0
1 F - -
2 F - -
3 F - -
4 F - -
5 F - -
6 F - -
7 F - -
8 F - -
BreadthFirstPaths Demo
Goal: Find shortest path between s and every other vertex.
1
2
3
4
5
6
7
8
0
Queue: []
v
s
# marked edgeTo distTo
0 T - 0
1 F - -
2 F - -
3 F - -
4 F - -
5 F - -
6 F - -
7 F - -
8 F - -
BreadthFirstPaths Demo
Goal: Find shortest path between s and every other vertex.
1
2
3
4
5
6
7
8
0
Queue: [1]
v
s
# marked edgeTo distTo
0 T - 0
1 T 0 1
2 F - -
3 F - -
4 F - -
5 F - -
6 F - -
7 F - -
8 F - -
BreadthFirstPaths Demo
Goal: Find shortest path between s and every other vertex.
1
2
3
4
5
6
7
8
0
Queue: []
v
s
# marked edgeTo distTo
0 T - 0
1 T 0 1
2 F - -
3 F - -
4 F - -
5 F - -
6 F - -
7 F - -
8 F - -
BreadthFirstPaths Demo
Goal: Find shortest path between s and every other vertex.
1
2
3
4
5
6
7
8
0
Queue: [2, 4]
v
s
# marked edgeTo distTo
0 T - 0
1 T 0 1
2 T 1 2
3 F - -
4 T 1 2
5 F - -
6 F - -
7 F - -
8 F - -
BreadthFirstPaths Demo
Goal: Find shortest path between s and every other vertex.
1
2
3
4
5
6
7
8
0
Queue: [4]
v
s
# marked edgeTo distTo
0 T - 0
1 T 0 1
2 T 1 2
3 F - -
4 T 1 2
5 F - -
6 F - -
7 F - -
8 F - -
BreadthFirstPaths Demo
Goal: Find shortest path between s and every other vertex.
1
2
3
4
5
6
7
8
0
Queue: [4, 5]
v
s
# marked edgeTo distTo
0 T - 0
1 T 0 1
2 T 1 2
3 F - -
4 T 1 2
5 T 2 3
6 F - -
7 F - -
8 F - -
BreadthFirstPaths Demo
Goal: Find shortest path between s and every other vertex.
1
2
3
4
5
6
7
8
0
Queue: [5]
v
s
# marked edgeTo distTo
0 T - 0
1 T 0 1
2 T 1 2
3 F - -
4 T 1 2
5 T 2 3
6 F - -
7 F - -
8 F - -
BreadthFirstPaths Demo
Goal: Find shortest path between s and every other vertex.
1
2
3
4
5
6
7
8
0
Queue: [5, 3]
v
s
# marked edgeTo distTo
0 T - 0
1 T 0 1
2 T 1 2
3 T 4 3
4 T 1 2
5 T 2 3
6 F - -
7 F - -
8 F - -
BreadthFirstPaths Demo
Goal: Find shortest path between s and every other vertex.
1
2
3
4
5
6
7
8
0
Queue: [3]
v
s
# marked edgeTo distTo
0 T - 0
1 T 0 1
2 T 1 2
3 T 4 3
4 T 1 2
5 T 2 3
6 F - -
7 F - -
8 F - -
BreadthFirstPaths Demo
Goal: Find shortest path between s and every other vertex.
1
2
3
4
5
6
7
8
0
Queue: [3, 6, 8]
v
s
# marked edgeTo distTo
0 T - 0
1 T 0 1
2 T 1 2
3 T 4 3
4 T 1 2
5 T 2 3
6 T 5 4
7 F - -
8 T 5 4
Note: distance to all items on queue is always k or k + 1 for some k. Here k = 3.
BreadthFirstPaths Demo
Goal: Find shortest path between s and every other vertex.
1
2
3
4
5
6
7
8
0
Queue: [6, 8]
v
s
# marked edgeTo distTo
0 T - 0
1 T 0 1
2 T 1 2
3 T 4 3
4 T 1 2
5 T 2 3
6 T 5 4
7 F - -
8 T 5 4
BreadthFirstPaths Demo
Goal: Find shortest path between s and every other vertex.
1
2
3
4
5
6
7
8
0
Queue: [6, 8]
v
Nothing to add!
s
# marked edgeTo distTo
0 T - 0
1 T 0 1
2 T 1 2
3 T 4 3
4 T 1 2
5 T 2 3
6 T 5 4
7 F - -
8 T 5 4
BreadthFirstPaths Demo
Goal: Find shortest path between s and every other vertex.
1
2
3
4
5
6
7
8
0
Queue: [8]
v
s
# marked edgeTo distTo
0 T - 0
1 T 0 1
2 T 1 2
3 T 4 3
4 T 1 2
5 T 2 3
6 T 5 4
7 F - -
8 T 5 4
BreadthFirstPaths Demo
Goal: Find shortest path between s and every other vertex.
1
2
3
4
5
6
7
8
0
Queue: [8, 7]
v
s
# marked edgeTo distTo
0 T - 0
1 T 0 1
2 T 1 2
3 T 4 3
4 T 1 2
5 T 2 3
6 T 5 4
7 T 6 5
8 T 5 4
BreadthFirstPaths Demo
Goal: Find shortest path between s and every other vertex.
1
2
3
4
5
6
7
8
0
Queue: [7]
v
s
# marked edgeTo distTo
0 T - 0
1 T 0 1
2 T 1 2
3 T 4 3
4 T 1 2
5 T 2 3
6 T 5 4
7 T 6 5
8 T 5 4
BreadthFirstPaths Demo
Goal: Find shortest path between s and every other vertex.
1
2
3
4
5
6
7
8
0
Queue: [7]
v
Nothing to add!
s
# marked edgeTo distTo
0 T - 0
1 T 0 1
2 T 1 2
3 T 4 3
4 T 1 2
5 T 2 3
6 T 5 4
7 T 6 5
8 T 5 4
BreadthFirstPaths Demo
Goal: Find shortest path between s and every other vertex.
1
2
3
4
5
6
7
8
0
Queue: []
v
s
# marked edgeTo distTo
0 T - 0
1 T 0 1
2 T 1 2
3 T 4 3
4 T 1 2
5 T 2 3
6 T 5 4
7 T 6 5
8 T 5 4
BreadthFirstPaths Demo
Goal: Find shortest path between s and every other vertex.
1
2
3
4
5
6
7
8
0
Queue: []
v
Nothing to add!
s
# marked edgeTo distTo
0 T - 0
1 T 0 1
2 T 1 2
3 T 4 3
4 T 1 2
5 T 2 3
6 T 5 4
7 T 6 5
8 T 5 4
BreadthFirstPaths Implementation
Lecture 23, CS61B, Fall 2023
The All Paths Problem
The All Shortest Paths Problem
Graph Implementations and Runtime
Project 2B Note
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 |
Graph Implementations and Runtime
Lecture 23, CS61B, Fall 2023
The All Paths Problem
The All Shortest Paths Problem
Graph Implementations and Runtime
Project 2B Note
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.
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/pretty
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
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);
}
}
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);
}
}
} ...
}
This is a lot to digest!
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 |
Project 2B Note
Lecture 23, CS61B, Fall 2023
The All Paths Problem
The All Shortest Paths Problem
Graph Implementations and Runtime
Project 2B Note
Project Note
On project 2B, you cannot import the Princeton Graphs library.
Note: You may not need a separate Graph class. Whether you have one is up to you and your partner.
Summary
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.
BFS: Uses a queue instead of recursion to track what work needs to be done.
Choice of implementation has big impact on runtime and memory usage!