Thread: Graph Tour

  1. #1
    DeletedUserAccount
    Guest

    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. #2
    -bleh-
    Join Date
    Aug 2010
    Location
    somewhere in this universe
    Posts
    463
    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.
    Last edited by nimitzhunter; 02-13-2011 at 11:08 PM.
    "All that we see or seem
    Is but a dream within a dream." - Poe

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

  4. #4
    -bleh-
    Join Date
    Aug 2010
    Location
    somewhere in this universe
    Posts
    463
    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);
         already_traveled.push(x);
         travel(y);
    Last edited by nimitzhunter; 02-13-2011 at 11:22 PM.
    "All that we see or seem
    Is but a dream within a dream." - Poe

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Graph implementation
    By tcoffee in forum C Programming
    Replies: 10
    Last Post: 11-16-2010, 09:52 AM
  2. C++ graph ploting
    By ivpavic in forum C++ Programming
    Replies: 1
    Last Post: 05-26-2010, 12:06 PM
  3. error help making no sense
    By tunerfreak in forum C++ Programming
    Replies: 5
    Last Post: 04-17-2007, 07:55 PM
  4. determining a path through the graph
    By Mist in forum C Programming
    Replies: 2
    Last Post: 02-27-2005, 12:21 PM
  5. Minimize crossing edges in undirected graph
    By Shiro in forum C Programming
    Replies: 0
    Last Post: 12-26-2001, 04:48 AM