CS61B, 2021
Lecture 21: Graphs and Traversals ¡ñ Tree Traversals
¡ñ Graphs
¡ñ Depth First Search
¡ñ Breadth First Search
datastructur.es
Trees and Traversals
datastructur.es
Tree Definition (Reminder)
A tree consists of:
¡ñ A set of nodes.
¡ñ A set of edges that connect those nodes.
¡ð Constraint: There is exactly one path between any two nodes. Green structures below are trees. Pink ones are not.
datastructur.es
Rooted Trees Definition (Reminder)
A rooted tree is a tree where we¡¯ve chosen one node as the ¡°root¡±.
¡ñ Every node N except the root has exactly one parent, defined as the first node on the path from N to the root.
¡ñ A node with no child is called a leaf.
AA
A
BB
CCC
For each of these:
¡ñ A is the root.
¡ñ B is a child of A.
¡ñ A is a parent of B.
(and C of B) (and B of C)
B
C
datastructur.es
Trees
We¡¯ve seen trees as nodes in a specific data structure implementation: Search Trees, Tries, Heaps, Disjoint Sets, etc.
datastructur.es
Trees
Trees are a more general concept.
¡ñ Organization charts.
¡ñ Family lineages* including phylogenetic trees.
¡ñ MOH Training Manual for Management of Malaria.
*: Not all family lineages are trees!
datastructur.es
Example: File System Tree
Sometimes you want to iterate over a tree. For example, suppose you want to find the total size of all files in a folder called 61b.
¡ñ ¡ñ
What one might call ¡°tree iteration¡± is actually called ¡°tree traversal.¡± Unlike lists, there are many orders in which we might visit the nodes.
¡ð
Each ordering is useful in different ways.
61b
…
proj0
data
…
…
hw1
synthesizer spec
audio
…
planets.txt
…
GuitarHeroLite.java
1251 bytes
karplus-strong.png
851 bytes
hw1.md
23433 bytes
16180 bytes
datastructur.es
Tree Traversal Orderings
Level Order
¡ñ Visit top-to-bottom, left-to-right (like reading in English): DBFACEG
D
B
F
EG
AC
datastructur.es
Tree Traversal Orderings
Level Order
¡ñ Visit top-to-bottom, left-to-right (like reading in English): DBFACEG
Depth First Traversals
¡ñ 3 types: Preorder, Inorder, Postorder
¡ñ Basic (rough) idea: Traverse ¡°deep nodes¡± (e.g. A) before shallow ones (e.g. F).
¡ñ Note: Traversing a node is different than ¡°visiting¡± a node. See next slide.
D
B
F
EG
AC
datastructur.es
Depth First Traversals
Preorder: ¡°Visit¡± a node, then traverse its children:
D B A C F E G
preOrder(BSTNode x) {
if (x == null) return;
print(x.key)
preOrder(x.left)
preOrder(x.right)
}
D
B
F
AC
EG
datastructur.es
Depth First Traversals
Preorder traversal: ¡°Visit¡± a node, then traverse its children: DBACFEG
Inorder traversal: Traverse left child, visit, then traverse right child:
A B C D E F G
inOrder(BSTNode x) {
if (x == null) return;
inOrder(x.left)
print(x.key)
inOrder(x.right)
}
preOrder(BSTNode x) {
if (x == null) return;
print(x.key)
preOrder(x.left)
preOrder(x.right)
}
D
B
F
EG
AC
datastructur.es
Depth First Traversals http://yellkey.com/hand
Preorder traversal: ¡°Visit¡± a node, then traverse its children: DBACFEG Inorder traversal: Traverse left child, visit, traverse right child: ABCDEFG Postorder traversal: Traverse left, traverse right, then visit: ???????
postOrder(BSTNode x) {
if (x == null) return;
postOrder(x.left)
postOrder(x.right)
print(x.key)
}
1. DBACEFG 2. GFEDCBA 3. GEFCABD 4. ACBEGFD 5. ACBFEGD 6. Other
D
B
F
EG
AC
datastructur.es
Depth First Traversals
Preorder traversal: ¡°Visit¡± a node, then traverse its children: DBACFEG Inorder traversal: Traverse left child, visit, traverse right child: ABCDEFG Postorder traversal: Traverse left, traverse right, then visit: ACBEGFD
postOrder(BSTNode x) {
if (x == null) return;
postOrder(x.left)
postOrder(x.right)
print(x.key)
}
1. DBACEFG 2. GFEDCBA 3. GEFCABD 4. ACBEGFD 5. ACBFEGD 6. Other
D
B
F
EG
AC
datastructur.es
A Useful Visual Trick (for Humans, Not Algorithms)
¡ñ Preorder traversal: We trace a path around the graph, from the top going counter-clockwise. ¡°Visit¡± every time we pass the LEFT of a node.
¡ñ Inorder traversal: ¡°Visit¡± when you cross the bottom of a node.
¡ñ Postorder traversal: ¡°Visit¡± when you cross the right a node.
Example: Post-Order Traversal ¡ñ 4 78 52 963 1
1
2
45
3
6
789
datastructur.es
What Good Are All These Traversals?
Example: Preorder Traversal for printing directory listing:
directOverlay
directIO directO.suo
sc2APM
notes
directO.sln
python
printAPM.py
DXHookD3D11.cs Injector.cs
datastructur.es
What Good Are All These Traversals?
Example: Postorder Traversal for gathering file sizes.
postOrder(BSTNode x) {
if (x == null) return 0;
int total = 0;
for (BSTNode c : x.children())
total += postOrder(c)
total += x.fileSize();
return total;
}
directIO
directOverlay
38912
directO.suo
8798
sc2APM
324
notes
881
directO.sln
python
874
printAPM.py
18381
DXHookD3D11.cs
Injector.cs
datastructur.es
What Good Are All These Traversals?
Example: Postorder Traversal for gathering file sizes.
postOrder(BSTNode x) {
if (x == null) return 0;
int total = 0;
for (BSTNode c : x.children())
total += postOrder(c)
total += x.fileSize();
return total;
}
68170
sc2APM
66972 324
874
27179
directIO
directOverlay
38912
directO.suo
8798
notes python 881 874
directO.sln printAPM.py
18381
DXHookD3D11.cs
Injector.cs
datastructur.es
Graphs
datastructur.es
Trees and Hierarchical Relationships
Trees are fantastic for representing strict hierarchical relationships. ¡ñ But not every relationship is hierarchical.
¡ñ Example: Paris Metro map. This is not a tree: Contains cycles!
¡ñ More than one way to get from A to B.
B
A
datastructur.es
Tree Definition (Revisited)
A tree consists of:
¡ñ A set of nodes.
¡ñ A set of edges that connect those nodes.
¡ð Constraint: There is exactly one path between any two nodes. Green structures on slide are trees. Pink ones are not.
datastructur.es
Graph Definition
A graph consists of:
¡ñ A set of nodes.
¡ñ A set of zero or more edges, each of which connects two nodes.
Green structures below are graphs.
¡ñ Note, all trees are graphs!
datastructur.es
Graph Example: BART
Is the BART graph a tree?
datastructur.es
Graph Example: BART
Is the BART graph a tree?
¡ñ No, has one cycle. ¡ð San Bruno
¡ð SFO
¡ð Millbrae
datastructur.es
Graph Definition
A simple graph is a graph with:
¡ñ No edges that connect a vertex to itself, i.e. no ¡°loops¡±.
¡ñ No two edges that connect the same vertices, i.e. no ¡°parallel edges¡±. Green graph below is simple, pink graphs are not.
datastructur.es
Graph Definition
A simple graph is a graph with:
¡ñ No edges that connect a vertex to itself, i.e. no ¡°loops¡±.
¡ñ No two edges that connect the same vertices, i.e. no ¡°parallel edges¡±.
In 61B, unless otherwise explicitly stated, all graphs will be simple.
¡ñ In other words, when we say ¡°graph¡±, we mean ¡°simple graph.¡±
datastructur.es
Graph Types
Directed Undirected
bbe
Acyclic: a d a d cc
With Edge Labels
b3e 11
a2d c
Cyclic:
bb
adad
cc
datastructur.es
Graph Terminology
¡ñ Graph:
¡ð Set of vertices, a.k.a. nodes.
¡ð Set of edges: Pairs of vertices.
¡ð Vertices with an edge between are
adjacent.
¡ð Optional: Vertices or edges may have
labels (or weights).
¡ñ A path is a sequence of vertices connected by
edges.
¡ð A simple path is a path without repeated
vertices.
¡ñ A cycle is a path whose first and last vertices
are the same.
¡ð A graph with a cycle is ¡®cyclic¡¯.
¡ñ Two vertices are connected if there is a path between them. If all vertices are connected, we say the graph is connected.
Figure from Algorithms 4th Edition
datastructur.es
Graph Example: The Paris Metro
This schematic map of the Paris Metro is a graph:
¡ñ Undirected ¡ñ Connected
¡ñ Cyclic (not a tree!)
¡ñ Vertex-labeled (each has a color).
datastructur.es
Directed Graph Example
Not a tree!
¡ñ Two paths from
group_action to event.
Edge captures ¡®is-a-type-of¡¯ relationship. Example: descent is-a-type-of movement.
datastructur.es
Graph Problems
datastructur.es
Graph Queries
There are lots of interesting questions we can ask about a graph:
¡ñ What is the shortest route from S to T? What is the longest without cycles?
¡ñ Are there cycles?
¡ñ Is there a tour you can take that
only uses each node (station)
exactly once?
¡ñ Is there a tour that uses each edge
exactly once?
T
S
datastructur.es
Graph Queries More Theoretically
Some well known graph problems and their common names:
¡ñ s-t Path. Is there a path between vertices s and t?
¡ñ Connectivity. Is the graph connected, i.e. is there a path between all vertices?
¡ñ Biconnectivity. Is there a vertex whose removal disconnects the graph?
¡ñ Shortest s-t Path. What is the shortest path between vertices s and t?
¡ñ Cycle Detection. 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?
¡ñ Planarity. Can you draw the graph on paper with no crossing edges?
¡ñ Isomorphism. Are two graphs isomorphic (the same graph in disguise)?
Often can¡¯t tell how difficult a graph problem is without very deep consideration.
datastructur.es
Graph Problem Difficulty
Some well known graph problems:
¡ñ Euler Tour. Is there a cycle that uses every edge exactly once?
¡ñ Hamilton Tour. Is there a cycle that uses every vertex exactly once? Difficulty can be deceiving.
¡ñ An efficient Euler tour algorithm O(# edges) was found as early as 1873 [Link].
¡ñ Despite decades of intense study, no efficient algorithm for a Hamilton tour
exists. Best algorithms are exponential time.
Graph problems are among the most mathematically rich areas of CS theory.
datastructur.es
Depth-First Traversal
datastructur.es
s-t Connectivity
Let¡¯s solve a classic graph problem called the s-t connectivity problem.
¡ñ Given source vertex s and a target vertex t, is there a path between s and t?
Requires us to traverse the graph somehow.
0
1
4
s
3
6
7
t
2
5
8
datastructur.es
s-t Connectivity
Let¡¯s solve a classic graph problem called the s-t connectivity problem.
¡ñ Given source vertex s and a target vertex t, is there a path between s and t?
Requires us to traverse the graph somehow.
¡ñ Try to come up with an algorithm for connected(s, t).
0
1
4
s
3
6
7
t
2
5
8
datastructur.es
s-t Connectivity
One possible recursive algorithm for connected(s, t).
¡ñ Does s == t? If so, return true.
¡ñ Otherwise, if connected(v, t) for any neighbor v of s, return true.
¡ñ Return false.
What is wrong with the algorithm above?
3
6
7
t
0
1
4
s
2
5
8
datastructur.es
s-t Connectivity
One possible recursive algorithm for connected(s, t).
¡ñ Does s == t? If so, return true.
¡ñ Otherwise, if connected(v, t) for any neighbor v of s, return true.
¡ñ Return false.
What is wrong with the algorithm above?
3
6
7
t
0
1
4
s
2
5
8
datastructur.es
s-t Connectivity
One possible recursive algorithm for connected(s, t).
¡ñ Does s == t? If so, return true.
¡ñ Otherwise, if connected(v, t) for any neighbor v of s, return true.
¡ñ Return false.
What is wrong with it? Can get caught in an infinite loop. Example:
3
6
¡ñ connected(0, 7):
¡ð Does 0 == 7? No, so…
¡ð if (connected(1, 7)) return true;
¡ñ connected(1, 7):
¡ð Does 1 == 7? No, so…
¡ð If (connected(0, 7)) … ¡û Infinite loop.
s
0
1
4
2 5 8
7
t
datastructur.es
s-t Connectivity
One possible recursive algorithm for connected(s, t).
¡ñ Does s == t? If so, return true.
¡ñ Otherwise, if connected(v, t) for any neighbor v of s, return true.
¡ñ Return false.
What is wrong with it? Can get caught in an infinite loop. ¡ñ How do we fix it?
3
6
7
t
0
1
4
s
2
5
8
datastructur.es
s-t Connectivity
One possible recursive algorithm for connected(s, t).
¡ñ Mark s.
¡ñ Does s == t? If so, return true.
¡ñ Otherwise, if connected(v, t) for any unmarked neighbor v of s, return true.
¡ñ Return false.
Basic idea is same as before, but visit each vertex at most once.
3
6
7
t
¡ñ Marking nodes prevents multiple visits.
¡ñ Demo: Recursive s-t connectivity.
s
0
1
4
2
5
8
datastructur.es
Depth First Traversal
This idea of exploring a neighbor¡¯s entire subgraph before moving on to the next neighbor is known as Depth First Traversal.
¡ñ Example: Explore 1¡¯s subgraph completely before using the edge 0-3.
¡ñ Called ¡°depth first¡± because you go as deep as possible.
s0
1347
2
5
6
8t
datastructur.es
Depth First Traversal
This idea of exploring a neighbor¡¯s entire subgraph before moving on to the next neighbor is known as Depth First Traversal.
¡ñ Example: Explore 1¡¯s subgraph completely before using the edge 0-3.
¡ñ Called ¡°depth first¡± because you go as deep as possible.
s0
1347
2
5
6
8t
Entirely possible for 1¡¯s subgraph to include 3!
¡ñ It¡¯s still depth first, since we¡¯re not using the
edge 0-3 until the subgraph is explored.
datastructur.es
From: https://xkcd.com/761/
datastructur.es
The Power of Depth First Search
DFS is a very powerful technique that can be used for many types of graph problems.
Another example:
¡ñ Let¡¯s discuss an algorithm that computes a path to every vertex.
¡ñ Let¡¯s call this algorithm DepthFirstPaths.
¡ñ Demo: DepthFirstPaths.
datastructur.es
Tree Vs. Graph Traversals
datastructur.es
Tree Traversals
There are many tree traversals:
¡ñ Preorder: DBACFEG
¡ñ Inorder: ABCDEFG
¡ñ Postorder: ACBEGFD
¡ñ Level order: DBFACEG
D
B
AC
F
EG
datastructur.es
Graph Traversals
There are many tree traversals:
¡ñ Preorder: DBACFEG
¡ñ Inorder: ABCDEFG
¡ñ Postorder: ACBEGFD
¡ñ Level order: DBFACEG
D
B
AC
F
EG
3
6
7
datastructur.es
What we just did in DepthFirstPaths is called ¡°DFS Preorder.¡±
¡ñ DFS Preorder: Action is before DFS calls to neighbors. ¡ð Our action was setting edgeTo.
¡ð Example: edgeTo[1] was set before DFS calls to neighbors 2 and 4.
s
0
1
4
¡ñ One valid DFS preorder for this graph: 012543678 ¡ð Equivalent to the order of dfs calls.
2
5
8
Graph Traversals
There are many tree traversals:
¡ñ Preorder: DBACFEG
¡ñ Inorder: ABCDEFG
¡ñ Postorder: ACBEGFD
¡ñ Level order: DBFACEG
Could also do actions in DFS Postorder.
D
B
AC
F
EG
3
6
7
datastructur.es
¡ñ DFS Postorder: Action is after DFS calls to neighbors.
¡ñ Example: dfs(s):
¡ð mark(s)
¡ð For each unmarked neighbor n of s, dfs(n) ¡ð print(s)
¡ñ Results for dfs(0) would be: 347685210
¡ñ Equivalent to the order of dfs returns.
s
0
1
4
2
5
8
Graph Traversals
Just as there are many tree traversals:
¡ñ Preorder: DBACFEG
¡ñ Inorder: ABCDEFG
¡ñ Postorder: ACBEGFD
¡ñ Level order: DBFACEG
D
B
AC
F
EG
3
6
7
So too are there many graph traversals, given some source:
¡ñ DFS Preorder: 012543678 (dfs calls).
¡ñ DFS Postorder: 347685210 (dfs returns).
0
1
4
s
2
5
datastructur.es
8
Graph Traversals
Just as there are many tree traversals:
¡ñ Preorder: DBACFEG
¡ñ Inorder: ABCDEFG
¡ñ Postorder: ACBEGFD
¡ñ Level order: DBFACEG
D
B
AC
F
EG
3
6
7
datastructur.es
So too are there many graph traversals, given some source:
¡ñ DFS Preorder: 012543678 (dfs calls).
¡ñ DFS Postorder: 347685210 (dfs returns).
¡ñ BFS order: Act in order of distance from s.
s
0
1
4
¡ð BFS stands for ¡°breadth first search¡±.
¡ð Analogous to ¡°level order¡±. Search is wide, not deep.
¡ð 0 1 24 53 68 7
2
5
8
Shortest Paths Challenge Before Next Lecture
s
1
2
3
4
7
5
6
Goal: Given the graph above, find the length of the shortest path from s to all other vertices.
¡ñ Give a general algorithm.
¡ñ Hint: You¡¯ll need to somehow visit vertices in BFS order.
¡ñ Hint #2: You¡¯ll need to use some kind of data structure.
Will discuss a solution in the next lecture.
0
datastructur.es
Summary
datastructur.es
Summary
Graphs are a more general idea than a tree.
¡ñ A tree is a graph where there are no cycles and every vertex is connected.
¡ñ Key graph terms: Directed, Undirected, Cyclic, Acyclic, Path, Cycle. Graph problems vary widely in difficulty.
¡ñ Common tool for solving almost all graph problems is traversal.
¡ñ A traversal is an order in which you visit / act upon vertices.
¡ñ Tree traversals:
¡ð Preorder, inorder, postorder, level order. ¡ñ Graph traversals:
¡ð DFS preorder, DFS postorder, BFS.
¡ñ By performing actions / setting instance variables during a graph (or tree)
traversal, you can solve problems like s-t connectivity or path finding.
datastructur.es