DFS discovery and finish times
Suppose that we perform DFS on this graph by obeying the following rules:
• Start from vertex 1.
• At every vertex, process its out-neighbors in ascending order of id.
• Whenever we need to restart, do it from the white vertex with the smallest id
Show the resulting DFS forest. Furthermore, for every vertex, indicate its discovery time and finish time. also #/ = discovered and #/# = finished
dfs tree as follows:
6
|
1--2--7--3--4--5--8
the question ask me to show the resulting forest, yet I'm only producing one tree, what have i done wrong?
You have missed nothing. A forest is a set of graphs and thus even allowed to contain 0 graphs. So the graph-forst in your result is absolutely valid. Some lecturers tend to use their own definition though, so I'd advise to double check that with your script. As for the DFS-traversal it's perfectly valid and pretty simple to show that there exists a path from 1 to any node in the tree