Hints for Lab 2

Topological Sort:

Colors translate to visiting states of an object. Say blue means unvisited, yellow means visited and done, and red means processing a visit (an object is not visited until it is output in order). Thus, we may want to mark objects as unvisited, visited, or being visited. We will need a stack. We can put an object on a stack and take an object off a stack. We may assume all objects have a list of dependencies. We need the stack to remember what object we need to return to after visiting one of its dependencies. Only unvisited or visiting objects should be put on the stack. Visited objects should never be stacked. Worry about finding dependent objects that are not unvisited. When all dependencies are taken care of output the 'current' object.

 

Minimum Cost Network:

Define a matrix object called solution which is initially empty. Consider cables in increasing order of cost: for each cable, test whether its endpoints are already connected by cables in the solution; if not, add the cable to the solution matrix. Otherwise toss the cable and move on to the next one. The test is easy if every city has a group number with the meaning that two cities are connected by cables already in the solution if and only if their group numbers are identical. Group numbers can be assigned before testing cables. A simple way to do this is to assign a group number that is the same as the city number. When a cable is added to the solution the groups numbers of some of the cities (those with the same group number as one of the end cities) must be changed (to the group number of the other end city).