COMP 250
INTRODUCTION TO COMPUTER SCIENCE
Week 14-1 : Graphs 2
Giulia Alberini, Fall 2020 Slides adapted from Michael Langer’s
WHAT ARE WE GOING TO DO IN THIS VIDEO?
Recursive graph traversal depth first
Non-recursive graph traversal depth first
breadth first
RECALL: TREETRAVERSAL (RECURSIVE)
depthFirst_Tree (root){
if (root is not empty){
visit root // preorder for each child of root
depthfirst_Tree( child ) }
}
GRAPHTRAVERSAL (RECURSIVE)
Need to specify a starting vertex.
Visit all nodes that are “reachable” by a path from a starting vertex.
g bh
a
cf
d
e
GRAPH TRAVERSAL (RECURSIVE)
depthFirst_Graph (v){
v.visided = true
for each w such that (v,w) is in E
// i.e. v.adjList.contains(w) returns true
?? }
GRAPH TRAVERSAL (RECURSIVE)
depthFirst_Graph (v){
v.visided = true
visit v // do something with v
for each w such that (v,w) is in E // i.e. for each w in v.adjList
if !(w.visited) // avoid cycles!
dephFirst_Graph(w)
}
CALL STACK FOR depthFirst(a) a
eg cf
d
bh
depthFirst_Graph (v){
v.visided = true
for each w s.t. (v,w) is in E
}
if !(w.visited)
dephFirst_Graph(w)
a
CALL STACK FOR depthFirst(a) a
eg cf
d
bh
depthFirst_Graph (v){
v.visided = true
for each w s.t. (v,w) is in E
}
if !(w.visited)
dephFirst_Graph(w)
c aa
CALL STACK FOR depthFirst(a) a
eg cf
d
bh
depthFirst_Graph (v){
v.visided = true
for each w s.t. (v,w) is in E
}
if !(w.visited)
dephFirst_Graph(w)
f cc
aaa
CALL STACK FOR depthFirst(a) a
eg c f
d
b ff
ccc aaaa
bh
depthFirst_Graph (v){
v.visided = true
for each w s.t. (v,w) is in E
}
if !(w.visited)
dephFirst_Graph(w)
CALL STACK FOR depthFirst(a) a
eg cf
d
b fff
cccc aaaaa
bh
depthFirst_Graph (v){
v.visided = true
for each w s.t. (v,w) is in E
}
if !(w.visited)
dephFirst_Graph(w)
CALL STACK FOR depthFirst(a) a
eg cf
d
bh
be ffff
depthFirst_Graph (v){
v.visided = true
for each w s.t. (v,w) is in E
}
if !(w.visited)
dephFirst_Graph(w)
ccccc aaaaaa
CALL STACK FOR depthFirst(a) a
eg cf
d
bh
depthFirst_Graph (v){
v.visided = true
for each w s.t. (v,w) is in E
}
if !(w.visited) dephFirst_Graph(w)
be fffff
ccccccc aaaaaaaaa
CALL TREE
root
a
d
eg cf
bh
be fffff
ccccccc aaaaaaaaa
GRAPH TRAVERSALS
Unlike tree traversal for rooted tree, a graph traversal started from some arbitrary vertex does not necessarily reach all other vertices.
Knowing which vertices can be reached by a path from some starting vertex is itself an important problem. You will learn about such graph `connectivity’ problems in COMP 251.
The order of nodes visited depends on the order of nodes in the adjacency lists.
EXAMPLE 2
c d e f
Adjacency List
a – (b,d)
b – (a,c,e) c – (b,f)
d – (a,e,g) e – (b,d,f,h) f – (c,e,i)
g – (d,h)
h – (e,g,i)
i – (f,h)
ab
gh
i
EXAMPLE 2
ab de gh
c f i
What is the call tree for depthFirst(a) ?
(Do it in your head)
EXAMPLE 2
abcabc
f i
call tree for depthFirst(a)
defde
gh
igh
GRAPH TRAVERSALS
Q: Can we do non-recursive graph traversals?
GRAPH TRAVERSALS
Q: Can we do non-recursive graph traversals?
A: Yes, similar to tree traversal: use a stack or a queue.
RECALL: DEPTHFIRSTTREETRAVERSAL
(WITH A SLIGHT VARIATION)
treeTraversalUsingStack(root){ initialize empty stack s s.push(root)
while s is not empty {
cur = s.pop()
visit cur
for each child of cur {
s.push(child) }
} }
Visit a node after popping it from the stack.
Every node in the tree gets pushed, and popped, and visited.
GENERALIZE TO GRAPH
graphTraversalUsingStack(v){ initialize empty stack s v.visited = true s.push(v)
while s is not empty {
cur = s.pop()
visit cur // do something for each w in cur.adjList
}
} }
if(!w.visited) {
w.visited = true
s.push(w) }
Indicate as “reached” a node before pushing it onto the
stack. We do that by updating the field visited.
Visit the node (perform some operations) after it gets popped from the stack.
Every node in the graph gets reached, pushed, popped, and visited.
EXAMPLE: graphTraversalUsingStack(a)
c f i
Order of visit: a a
ab de gh
a
EXAMPLE: graphTraversalUsingStack(a)
c f i
Order of visit: a ab
d
ab de gh
d a_bb
EXAMPLE: graphTraversalUsingStack(a)
c
Order of visit: ad ab
ab
def de ghi g
g de
a_bbbb
EXAMPLE: graphTraversalUsingStack(a)
c
Order of visit: adg ab
ab
def de ghi gh
gh deee a_bbbbbb
EXAMPLE: graphTraversalUsingStack(a)
c
Order of visit: adgh ab
ab
def de ghi ghi
ghi d eeeee
a_bbbbbbbb
EXAMPLE: graphTraversalUsingStack(a)
c
Order of visit: adghi ab
ab
def def ghi ghi
ghif d eeeeeee
a_bbbbbbbbbb
EXAMPLE: graphTraversalUsingStack(a)
abc abc
def def
ghi ghi
ghifc d eeeeeeeee a_bbbbbbbbbbbb
Order of visit: adghif
EXAMPLE: graphTraversalUsingStack(a)
abc abc
def def
ghi ghi
ghifc
d eeeeeeeeee
Order of visit: adghifceb
a_bbbbbbbbbbbbbb_
RECALL: BREADTHFIRSTTREETRAVERSAL
for each level i
visit all nodes at level i
treeTraversalUsingQueue(root){ initialize empty queue q q.enqueue(root)
while q is not empty {
cur = q.dequeue()
visit cur
for each child of cur
q.enqueue(child) }
}
a
b
c
d
e
f
g
h
i
j
k
BREADTH FIRST GRAPH TRAVERSAL
Given an input vertex, visit all vertices that can be reached by paths of length 1, 2, 3, 4, ….
BREADTH FIRST GRAPH TRAVERSAL
graphTraversalUsingQueue(v){ initialize empty queue q v.visited = true q.enqueue(v)
while q is not empty {
cur = q.dequeue()
for each w in cur.adjList {
if(!w.visited) {
w.visited = true
q.enqueue(w)
}
} }
}
EXAMPLE
graphTraversalUsingQueue(c) queue
c
a d
e cf
b
EXAMPLE
graphTraversalUsingQueue(c) queue
c f
a d
e cf
b
EXAMPLE
graphTraversalUsingQueue(c) queue
c
f be
Both ‘b’, ‘e’ are visited and enqueued before ‘b’ is dequeued.
a d
e cf
b
EXAMPLE
graphTraversalUsingQueue(c) queue
c
f be e _
a d
e cf
b
EXAMPLE
graphTraversalUsingQueue(c) a
d
e cf
b
It defines a tree whose root is the starting vertex. It finds the shortest path (number of edges) to all vertices reachable from the starting vertex.
EXAMPLE: graphTraversalUsingQueue(a)
a
ab de gh
c f i
EXAMPLE: graphTraversalUsingQueue(a)
a bd
ab de gh
c f i
EXAMPLE: graphTraversalUsingQueue(a)
a bd dce
ab de gh
c f i
EXAMPLE: graphTraversalUsingQueue(a)
a bd dce
c
d e f ceg
i
ab
gh
EXAMPLE: graphTraversalUsingQueue(a)
a bd dce
ab
c
d e f ceg egf
i
gh
EXAMPLE: graphTraversalUsingQueue(a)
a bd dce
ab
c
d e f ceg egf
gfh
gh
i
EXAMPLE: graphTraversalUsingQueue(a)
a bd dce
ab
c
d e f ceg egf
gfh fh hi
gh
i
EXAMPLE: graphTraversalUsingQueue(a) 124
abc
a bd
3 5 7f dce de ceg
6g8h9i
egf gfh fh hi
i _
Note order of nodes visited: We get paths of length 1, the paths of length 2, etc.
i.e. breadth first.
RECALL: HOW TO IMPLEMENT A GRAPH CLASS IN JAVA?
class Graph
class Vertex
ArrayList
T element;
boolean visited;
}
class Edge {
Vertex endVertex;
double weight;
: }
}
PRIOR TO TRAVERSAL!
for each w in V
w.visited = false
How should we implement this?
PRIOR TO TRAVERSAL!
for each w in V
w.visited = false
class Graph
public void resetVisited() {
} }
PRIOR TO TRAVERSAL!
for each w in V
w.visited = false
class Graph
public void resetVisited() {
for(Vertex
v.visited = false;
} }