# Graph Tour

This is a discussion on Graph Tour within the C Programming forums, part of the General Programming Boards category; I am working on this lab right now. I've figured out how to populate my graph (not from the command ...

1. ## Graph Tour

I am working on this lab right now. I've figured out how to populate my graph (not from the command line yet, but I am certain that won't be hard), and I am currently working on the algorithm that will allow me to "walk" the graph and find some tour.

After a few hours of unsuccessful implementations, Google searches, and thrown-away papers, I am beginning to think that I might not be able to find a solution if I want to sleep at all tonight.

Is there a popular algorithm for finding such a tour (visit all vertices only once), and if so - what would be its rough outline? I am almost completely convinced that it can be implemented recursively with relative ease, but I can't seem to find the right recursion. And the only method that made sense to me on paper works with several nested for loops and extra arrays. Nasty business.

Any tips?

2. Prim's algorithm for MST. Don't have to recurse, just need to be a bit greedy. Just choose any vertex in your graph, look at all the edge that comes out of that vertex, and choose the one with the lowest weight. Then continue to do so until all the node are traversed.

Edit: actually, prim's just find the shortest path, it may not solve the TSP which i didn't see.
Edit 2: your problem is small enough, and it allows for failure. So let's be greedy about it. Start from any city, maintain a list of city that you already visit. We're still greedy, so we choose the edge with the lowest weight. Go to the new city, then check whether that city connect to any of the cities on the already travel lists. If all the there is no edges to a new city, quit the program. Actually, Plainfield is the only city that you can start from and allows you to traverse all other cities once. Starting from other cities should result in failure.

3. Moreover, how would I continue choosing the adjacent with the lowest weight without calling recursion?

4. Recursion and a loop are just similar in this case. You can use recursion if you want. I would maintain already_traveled as a stack to keep track of traveled cities.
Code:
```x in V;
travel(x)
if ( x in already_travel) break;
else
y = find_min_weight(x);