程序代写代做代考 Java graph C COMP 250

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 { ArrayList> vetexList;
class Vertex {
ArrayList adjList;
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 { ArrayList> vetexList; :
public void resetVisited() {
} }

PRIOR TO TRAVERSAL!
for each w in V
w.visited = false
class Graph { ArrayList> vetexList; :
public void resetVisited() {
for(Vertex v : vertexList)
v.visited = false;
} }