In question 6 we are required to use the DFS and BFS algorithms.

Can we assume that we have control over the adjacency list of the edges in G and that we are allowed to modify the order of edges within each vertex as we see fit?

Assume your input is read-only.

Now go ahead and do what you want. You can copy the whole input in linear time if you like, and manipulate it any way you like. Just take into consideration how long it takes you to manipulate things. If the complexity of some operation is obvious, you don't have to prove it. If you are not sure if it's obvious, prove it. If it takes you 10 seconds, then it was probably obvious, and you wasted 10 seconds, no big deal. If it takes you longer, it probably wasn't obvious, so good thing you proved it.

Sorry, but I didn't quite follow you:

1. I believe that for a given G, I can make a manipulated copy of it - G', so that I can print any spanning tree via DFS(G', v) for some v.

2. However, from reading the question it seems to me that I am required to use DFS(G, v) and not my manipulation, so there's not much point in building G' to begin with (since I can't use it in the DFS).

Simply put - If I can't yield some spanning tree of G via DFS(G) but I can yield all spanning trees of G via DFS(G') - does that still meet the criteria of the question?

P.S. - Since we are not required to give an algorithm, do I still need to give a complexity analysis? Can't I simply prove correctness?

Hi,

Okay, I think I see where the misunderstanding is. I think you understood that DFS must choose the edges in the order that it finds them in the adjacency list. That is not the case. Notice that in the description of DFS there is no mention even of the data structure used to hold the tree. The correctness of DFS doesn't depend on it, and whenever the DFS makes a choice, it can be arbitrary, because the correctness holds for any choice.

The complexity, on the other hand, obviously depends on this choice. Because we can choose some edge in O(1), the complexity of DFS is linear. If you implement DFS with a slower choice method, the correctness would still hold, but the complexity wouldn't.

So, as long as you are not trying to prove some property of DFS, and not bound the running time, if you want DFS to choose some edge, just let DFS choose it.When you reach a vertex and need to choose an edge, you can just read all the edges and choose the one that you feel like.

I hope this answers the question