Graphs
This week: Depth First Search and Topological Sort
Depth First Search
• Basic idea is to search through the graph going as ______ as possible
before we ________ to ________________
• Similar to BFS, each vertex is coloured as we go
• White
• Grey
• Black
• Instead of storing distance from source vertex, store ____________
• d[v]
• f[v]
Depth First Search
• Natural to write DFS recursively
• Because DFS is commonly used to find ___________________,
our main algorithm won’t take a source vertex but will call
____________ repeatedly on each _________________
Depth First Search
Chalk Talk
1: [2, 4, 7]
2: [3, 4]
3: [1, 4]
4: []
5: [4, 6]
6: [3, 5]
7: [1, 4]
v c 𝝅 d f
W9 Worksheet
Put your answers to Q1 and Q2 into the Google Doc row for your group
http://tinyurl.com/csc2635
http://tinyurl.com/csc2635
DFS: Complexity
DFS-VISIT only called on ___________ and then those vertices immediately
________________.
So DFS-VISIT called _____________ on each ______________.
Outside of recursive calls, each execution of _________________
Examines _______________ for _____________.
So total running time is ________________
DFS: forest
• _______________ (u,v) edges in the DFS-forest
v is __________ when edge (u,v) is examined
• _______________ (u,v) v is ancestor of u in DFS-forest
v is __________ when edge (u,v) is examined
• _______________ (u,v) v is descendant of u in the DFS-forest
v is __________ when edge (u,v) is examined
• _______________ (u,v) all other edges not part of DFS-forest, v is
neither ancestor nor descendant
v is __________ when edge (u,v) is examined
Chalk Talk v d f
1 1 10
2 2 7
3 3 6
4 4 5
5 11 14
6 12 13
7 8 9
W10 Worksheet Q1
Mark in the Google Doc row for your group when you are finished Q1
http://tinyurl.com/csc2635
Then go on to questions 2 and 4.
Leave question 3 for optional practice at home. I’m not expecting you
to finish 4d, but it would be good to look at 4 a-c before this breakout
ends. If you are watching the video, pause long enough to complete
questions 2 and 4a-c before continuing.
http://tinyurl.com/breakouts-2635
W10 Worksheet Q1 Discussion
Parenthesis Theorem
In any DFS of graph G, for any two vertices u and v, exactly one of these
3 conditions holds:
• The intervals [d[u],f[u]] and [d[v],f[v]] are entirely disjoint
• The interval [d[u],f[u]] is contained entirely in interval [d[v],f[v]]
• The interval [d[v],f[v] is contained entirely in interval [d[u],f[u]]
W10 Worksheet Q4 Discussion
W10 Worksheet Discussion
Topological Sort
• For directed acyclic graphs only
• A ______ ordering of all _______ in graph G
• Such that if G contains (u,v) then _________________________
• Algorithm:
Strongly Connected
• In an undirected graph, it is connected if
• We didn’t previously define “connected” for a directed graph
• Strongly connected in a directed graph means that
Strongly Connected Directed Graph
• Algorithm to test?
• In directed graph G=(V, E), a strongly-connected
component is the maximal set of vertices C ⊆ V
such that for every pair of vertices u and v in C, we
have
Chalk Talk