Exercise 11: Depth-First Search

Objectives

to use a graph ADT
to implement depth-first search

Introduction

We return yet again to our implementation of heuristics for the Travelling Salesperson Problem. Recall our greedy heuristic to the TSP program:

generate a list of all pairs of cities
sort that list in order of increasing distance, breaking ties arbitrarily
start with an empty partial tour
for each pair of cities, if they are not already connected by the partial tour and if each city in the pair is included in at most one other pair added previously, then add a segment between the two cities in the pair to the partial tour (these cities will end up adjacent to each other in the final tour)
arrange the segments to create the final tour.

The check whether each city in the pair is included in at most one other pair added previously means that in the step in our example when we check the pair SEA-MCI, we do not add the segment between those two cities because MCI already has segments to STL and DAL.

YVR-SEA, IAH-DAL-MCI-STL-DCA-BWI; check SEA-MCI

Instead, we skip pairs until we add SEA-YVR as the last segment.

YVR-SEA-IAH-DAL-MCI-STL-DCA-BWI

The check to make sure that each city is part of at most two selected segments ensures that the end result forms a single sequence of cities that we can form a complete tour from by adding the segment between its endpoints.

If we omit that check, we end up with the minimum spanning tree for the cities – a collection of selected segments such that all pairs of cities are connected using some sequence of those selected segments, and such that the total distance of all the selected segments is as small as possible. But because the end result is a tree instead of a simple path – there's a branch at MCI so that if you're coming from SEA you have a choice of whether to go to DAL or STL next – we must do some additional work to turn the minimum spanning tree into a tour.

YVR-SEA-IAH-DAL-MCI-STL-DCA-BWI

We can use depth-first search in order to turn the tree into a tour. Depth-first search is a backtracking graph exploration algorithm. The cities are the vertices in our graph and the selected segments are the edges. Depth-first search starts at some vertex in the graph and visits one of its neighbors. It then visits one of that neighbor's unvisited neighbors, one of that neighbor's neighbor's unvisited neighbors, and so on until there are no unvisited neighbors to visit next. At that point, it backtracks to the last point at where it still has a choice of another unvisited neighbor to visit, and visits that neighbor. The process continues until there are no vertices left to visit and we backtrack from the starting point. If the graph is connected – for every pair of vertices there is some path between them – then all vertices will be visited. Listing them in the order they were first visited and adding a segment between the last vertex and the starting point completes the tour.

So in our example, if we start at SEA then we can visit YVR or MCI first. If we choose YVR, we have nowhere to go from YVR and backtrack to SEA, from which we go to MCI. We have a choice of DAL or STL from MCI. If we choose STL then we go there and then to DCA and BWI, at which point we are stuck again and backtrack to DCA, from where there is nowhere else to go, and then to STL, from where the is nowhere else to go, and then to MCI, from which we can go to DAL. Once at DAL, we visit IAH. At that point we are stuck again and backtrack all the way past our starting point SEA, so we are done. We first visited the vertices in order SEA-YVR-MCI-STL-DCA-BWI-DAL-IAH and add IAH-SEA to complete the tour.

YVR-SEA--MCI-STL-DCA-BWI-DAL-IAH-SEA

Assignment

Update your TSP program to implement the minimum spanning tree heuristic when the first command-line argument is -mst. The tree should be converted into a tour by an execution of depth-first search starting at city 0 and visiting unvisited neighbors in order of increasing distance.

Code

Adjacency List implementation of the Undirected Graph ADT (`lugraph.c`)

Complete the lugraph_dfs function so that it implements depth-first search and returns the information about the execution and results of that search in a lug_search struct. The lugraph_dfs function should initialize a lug_search struct and pass that to a recursive helper function along with the starting vertex. The recursive helper function should

mark the current vertex as processing,
save the current vertex in the visited array in the lug_search struct,
iterate over the neighbors of the current vertex, making a recursive call on the unvisited ones and recording the current vertex as the predecessor of those unvisited neighbors (we won't use that for this TSP heuristic, but it can be helpful in other applications of DFS), and
mark the current vertex as finished (there is no difference between "processing" and "finished" for the MST heuristic, but the distinction can be helpful in other applications of DFS).

`tsp.c`

The implementation of the route_greedy in /c/cs223/hw11/Optional/tsp.c has been modified to use the undirected graph ADT to keep track of the degree of the vertices and to use depth-first search to order the segments into a path. You will need to either use your completed union_find.c from Exercise 6, or change the connectedness test to use lugraph_connected.

Add the route_mst function to compute a tour using the Minimum Spanning Tree heuristic. This function should start with a graph with $n$ vertices and no edges and then consider all possible pairs of cities in order of increasing distance between them. If the cities are not already connected in the graph then the corresponding edge should be added. When $n-1$ edges have been added, route_mst should call lugraph_dfs to turn the minimum spanning tree into a tour, and copy that tour into the array passed in as a parameter.

Examples and Output

If sea_6_dal.in contains

SEA
YVR
MCI
STL
BWI
DCA
IAH
DAL

then the output of running your program should be

(base) [jrg94@termite code]$ ./TSP -greedy sea_6_dal.in
 -greedy:   9711.84 SEA IAH DAL MCI STL DCA BWI YVR SEA
(base) [jrg94@termite code]$ ./TSP -mst sea_6_dal.in
    -mst:   9605.81 SEA YVR MCI STL DCA BWI DAL IAH SEA

Submissions

Submit your modified tsp.c and your lugraph.c files, your completed union_find.c from Exercise 6 (if necessary), any other files you created, a makefile with the TSP executable as the default target, and your log as assignment number 11. You need not submit the lugraph.h header file, or any of the other supporting files (and if you do, they will be ignored).