Prev     Next
Test for Cycles

Instructions: An important part of the algorithm is to be able to test whether a chosen power line should be added to the partial solution. This can be done by assigning group numbers to each city: two cities have the same group number if and only if they are connected by lines in the partial solution. Because no cities are connected initially, the group numbers of all cities are different. When a line is tested, the group numbers of the cities it directly connects are tested for equality. If so, the line is not added, otherwise it is. This can be seen in the applet above. Click the "Update" button. Two groups of cities are shown, every pair in each group is connected by lines that are in the partial solution. Click on "Solve" to see possible group numbers for each group. Click on "Switch" to see a green line that is to be tested. Since the group numbers of its end cities are different, the line should be added to the partial solution. But this means the group numbers of the group one end point is connected to must be changed to equal the group number of the cities originally in the group of the other end city. Click "Switch" again to see the group 5 cities changed to group 3 cities.