CS计算机代考程序代写 algorithm Graphs

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