are we supposed to prove that on the same graph, both BFS and DFS will give us the same tree, OR - every time we run a BFS on the graph we get the same result, and every time we run a DFS we get the same result (the two results are not connected)?
Date: 13 Nov 2014 17:14
Number of posts: 2
RSS: New posts
You are asked whether BFS and DFS will give the same tree.
(Note that every time BFS is run on any graph, it will output the same tree, as its choices are deterministic - arbitrary, but deterministic. It is, of course, possible to implement BFS using a random edge choice rule, but the standard version has a deterministic choice. The reason we don't specify any particular rule is because the proof holds for any collection of choices.)