Pre-Announcement
Brenley for Gill Tract Community Farm
Announcements
Pre-spring Break Extra Credit Survey due Friday at 11:59 PM.
Lab due this Friday will be released today for those of you travelling who want to get it in early.�
CS61B
Lecture 26: Graphs
Graph
Graph: A set of nodes (a.k.a. vertices) connected pairwise by edges.�
Graph Types
a
b
d
c
a
b
d
c
e
a
b
d
c
a
b
d
c
Acyclic:
Cyclic:
Directed
Undirected
With Edge Labels
b
d
c
e
a
1
2
3
1
Graph Terminology
Figure from Algorithms 4th Edition
Some Graph-Processing Problems
s-t Path. Is there a path between vertices s and t?
Shortest s-t Path. What is the shortest path between vertices s and t?
Cycle. Does the graph contain any cycles?
Euler Tour. Is there a cycle that uses every edge exactly once?
Hamilton Tour. Is there a cycle that uses every vertex exactly once?
Connectivity. Is the graph connected, i.e. is there a path between all vertex pairs?
Biconnectivity. Is there a vertex whose removal disconnects the graph?
Planarity. Can you draw the graph on a piece of paper with no crossing edges?
Isomorphism. Are two graphs isomorphic (the same graph in disguise)?
Graph problems: Unobvious which are easy, hard, or computationally intractable.
Graph Example: The Paris Metro
This subway map of Paris is:
Graph Example: BART
Is the BART graph a tree?��
Nodes: Cities. Edge Weights: ~Number of friends between cities
Nodes: Scientific Journals.
Edges:
Edge captures ‘is-a-type-of’ relationship. Example: descent is-a-type-of movement.
Graph Representations
Common Simplification: Integer Vertices
Common convention: Number nodes irrespective of label, and use number throughout the graph implementation. To lookup a vertex by label, use a Map<Label, Integer>.
Austin
Dallas
Houston
0
1
2
Intended graph.
What you get.
Map<String, Integer>
Austin: 0
Dallas: 1
Houston: 2
Graph API
Using a graph in Java:
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
Using a graph in Java:
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, 2) = 2
1
3
2
Graph Representations
0
1
2
| 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 Printing Runtime: http://shoutkey.com/from
What is the order of growth of the running time of the following code if the graph uses an adjacency-matrix representation, where V is the number of vertices, and E is the total number of edges?
How much time does adj take?
How many adj calls?
| 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
PollEverywhere: pollEv.com/jhug or text “jhug” to 37607
What is the order of growth of the running time of the following code if the graph uses an adjacency-matrix representation, where V is the number of vertices, and E is the total number of edges.
How much time does adj take?
How many adj calls?
| 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
PollEverywhere: pollEv.com/jhug or text “jhug” to 37607
What is the order of growth of the running time of the following code if the graph uses an adjacency-matrix representation, where V is the number of vertices, and E is the total number of edges.
�What does G.adj(1) return?
| 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
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://shoutkey.com/squeal
What is the order of growth of the running time of the following code if the graph uses an adjacency-list representation, where V is the number of vertices, and E is the total number of edges?
How much time does adj take?
How many adj calls?
a
b
c
0
1
2
[1, 2]
[2]
Graph Printing Runtime: http://shoutkey.com/squeal
What is the order of growth of the running time of the following code if the graph uses an adjacency-list representation, where V is the number of vertices, and E is the total number of edges?
How much time does adj take?
How many adj calls?
a
b
c
0
1
2
[1, 2]
[2]
Graph Printing Runtime: http://shoutkey.com/squeal
What is the order of growth of the running time of the following code if the graph uses an adjacency-list representation, where V is the number of vertices, and E is the total number of edges?
�If we count adj as our cost model: Θ(V)
If we count prints: Θ(E)
a
b
c
0
1
2
[1, 2]
[2]
Graph Printing Runtime: http://shoutkey.com/squeal
What is the order of growth of the running time of the following code if the graph uses an adjacency-list representation, where V is the number of vertices, and E is the total number of edges?
a
b
c
0
1
2
[1, 2]
[2]
Graph Representations
Runtime of some basic operations for each representation:
In practice, adjacency lists are most common.
idea | addEdge(s, t) | adj(s) | printgraph() | hasEdge(s, t) | space used |
adjacency matrix | Θ(1) | Θ(V) | Θ(V2) | Θ(1) | Θ(V2) |
list of edges | Θ(1) | Θ(E) | Θ(E) | Θ(E) | Θ(E) |
adjacency list | Θ(1) | Θ(1) | Θ(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];
}
}
Depth-First Traversal
Maze Traversal / s-t Path
Suppose we want to know if there exists a path from vertex s=0 to vertex t=7. What is wrong with the following recursive algorithm for connected(s, t)?
Example:
1
2
3
4
5
6
7
8
0
s
t
Improving Our Connectivity Algorithm
Goal: Search for a path from s to t, but visit each vertex at most once. To do this, we can mark each vertex as we search. Resulting algorithm for connected(s, t) is as follows:
1
2
3
4
5
6
7
8
0
s
t
Depth First Traversal
This idea of exploring the entire subgraph for each child is known as Depth First Traversal.
1
2
3
4
5
6
7
8
0
Or a more visceral example: https://xkcd.com/761/
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)
}
Implementing Paths With Depth First Search
To visit a vertex v:
Data Structures:
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
Demo: 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: How would we write hasPathTo(v)?
DepthFirstPaths Summary
Demo: DepthFirstPaths
Properties of Depth First Search: