Advice for Assignment 2

Important General Comment

Remember that all of the hints below are just that: hints! There is more than one correct way of solving every problem; in other words, you do not have to follow the hints: they are simply provided as a way to get you started, if you hadn't already figured out some of this stuff on your own.

• Monday 15 February:

  In your code for DFS, you need to keep track of the next edge to visit for every vertex on the stack. In lecture, I described this by keeping track of the edge number together with the vertex on the stack, but the "Node" data type in the code for the assignment only has room to store the Vertex number. So how do you also keep track of which edge to visit next from that vertex?

  Here's the idea: you don't have to store the number of the next edge to visit from a given vertex in the stack together with the vertex number; you can simply keep track of it separately... I'll let you work out how you can best do this, but it's relatively simple (in other words, if you can only think of some complicated way of doing this, you don't have the right idea; go back and think about it some more).

  (You might have thought to create a different type of "Node" specifically for DFS, but that would require you to duplicate a lot of code unecessarily and would almost certainly be considered a bad design decision.)

• Wednesday 10 February:

  For DFS and BFS, you need functions that perform `queue' and `stack' operations. Here's a hint: from the "graph.h" file, you already have a data type that can be used to store linked lists of Vertices, so all you need to do is write functions that manipulate these linked lists in the right way:

  • a function to insert a new node at the head of a list;
  • a function to insert a new node at the tail of a list;
  • a function to get the value stored in the node at the head of a list;
  • a function to get the value stored in the node at the tail of a list;
  • a function to remove the node at the head of a list;
  • a function to remove the node at the tail of a list.
  If you implement all these functions, you can easily perform all the operations needed in DFS and BFS.

  A note on design: if you do this, think carefully about where all those functions should be put. (Remember why we split up the program into multiple files in the first place...)

<Back to main page>