2. Consider the directed graph below. When I say \"do a heuristic DFS of the gra
ID: 3904558 • Letter: 2
Question
2. Consider the directed graph below. When I say "do a heuristic DFS of the graph", use edge ength as the heuristic and break ties alphabetically Part A: Find the discovery and finish times of the nodes Node Discovery Time Finishing Time Part B: Classify the edges as T (tree), F (forward), B (back), or C (cross) edges Edge AB AC AD BD BE CA CF DB DC DE DF DG EG FD GE Part C: Here's the graph G' (G with the edge directions reversed). Show the discovery times and finish times of the nodes when you do a heuristic DFS Node Discovery Time Finishing Time Part D [5 pts]: List the SCCs. (You may not need all the lines.) SCCsExplanation / Answer
PART A:
Node
A
B
C
D
E
F
G
Discovery time
0
1
4
3
18
6
17
Finish time
24
23
22
20
18
21
19
PART B:
Edge
AB
AC
AD
BD
BE
CA
CF
DB
DC
DE
DF
DG
EG
FD
GE
Type
F
C
F
C
F
C
F
C
F
F
C
F
C
C
C
PART C:
Node
A
B
C
D
E
F
G
Discovery time
0
4
1
2
-1
13
-1
Finish time
16
4
15
14
-1
13
-1
PART D:
SCCS : ACD ACFD ACFDB
Node
A
B
C
D
E
F
G
Discovery time
0
1
4
3
18
6
17
Finish time
24
23
22
20
18
21
19
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.