Graph theory - depth first search algorithm (will need to program this at some point but just can't seem to understand it)

Question

I have a mid-term (mock) exam in a few days and this is the only topic that I can't seem to get my head around. For example I have no idea how to do this question

How can I tell which vertices are visited in what order? I've looked online and found information about DFS, but nowhere have I seen the DFS-CC and DFS-PROC stuff we're doing.

Answer 1

In a program, you could use a square matrix to represent which vertices are connected. The rows and the columns represent the vertices. A zero would mean not connected and a 1 would mean connected. For example in graph G, row 1 column 3 would be 1 but row 1 column 7 would be 0. For graph G, there would be symmetry in the matrix because each connection has two directions. But you could have a more complicated graph with certain paths only going in one direction.

Answer 2

DFS has to start somewhere, so by "the vertices of G are considered in natural order" it starts at node 1. There are two node adjacent to node 1, namely node 2 and 3. Again by the same rule it chooses to visit node 2 first. Node 2 is connected to 1, 3, 4, and 5. But 1 has already been visited so it chooses 3. Node 3 is connected to 1, 2, and 5. Both 1 and 2 are visited, so 5. And from 5 to 4.

Therefore 1, 2, 3, 5, 4.

Now all connected nodes are already visited so the process starts again with a new node. Again by "considering in natural order" that means starting at 6. The rest of the traversal follows the same pattern. I hope you get the idea now - if not ask a more specific question.

Answer 3

You should definitely ask you prof about the meaning of DFS-CC and DFS-PROC. I have a book called "Digraphs: Theory, Algorithms and Applications" written by Jørgen Bang-Jensen, Gregory Z. Gutin, and in it I found the following definition:

Hope this might help.