USA: +1 (725) 712-1730 
Sign in
Request solve following problem on “Alogrithms”
Show the d and pi values that result from running depth-first search on the graph given in Fig. 1 using vertex 4 as the source.
Expert Answer
The DFS algorithm uses——–>
- d is used for time discovered
- f stands for time finished
- π – predecessor vertex
Given Figure ——>
DFS start from 4 —–>
4, 1, 2, 8, 9, 6, 7, 3
DFS figure ———->
Now d and pi value ——->
| 1 | 2 | 3 | 4 | 6 | 7 | 8 | 9 | |
| d | 2 | 4 | 9 | 1 | 7 | 8 | 5 | 6 |
| f | 3 | 12 | 10 | 11 | * | * | * | * |
| pi | 4 | 1,3,4 | 1 | 3 | 4,9 | 6 | 2,4,6 | 2,7,8 |
* It can never finished by DFS becasue predecessor node not finished(deadlock)
