which algo to use? graph theory...

This is a discussion on which algo to use? graph theory... within the C++ Programming forums, part of the General Programming Boards category; OK, so I have this assigment that I unfortunately have a late start on...the description could be found HERE As ...

  1. #1
    Registered User axon's Avatar
    Join Date
    Feb 2003
    Posts
    2,572

    which algo to use? graph theory...

    OK, so I have this assigment that I unfortunately have a late start on...the description could be found HERE

    As you can see, the very last instruction says that we have to develop our own data structure.

    I want to keep this within decent runtimes so I was thinking of using the Depth first search algo for most of the operations...I'm not sure, however, if that is the best option. Any thoughts? suggestions?

    some entropy with that sink? entropysink.com

    there are two cardinal sins from which all others spring: Impatience and Laziness. - franz kafka

  2. #2
    vae victus! skorman00's Avatar
    Join Date
    Nov 2003
    Posts
    594
    for your data structure, I would suggest a linked list of vertecies in the graph, each of which would also contain a linked list to all of its edges. I found that to be the best, especially if you're going to be adding and removing edges/vertices often. If you won't be doing that and you know every vertex has an edge to every other vertex, I'd say use a 2d array.

    Doing that though would not let you do any fancy traversals, so using a BSTs instead of a linked lists might be handy for you.

    Algorithms on how to find the shortest path's and such; I've blown blood vessels arguing this. It always came down to how often certain situations came to be, and personal preference. To avoid any of that, I'm going to say dabble around and see what you like.

  3. #3
    Registered User axon's Avatar
    Join Date
    Feb 2003
    Posts
    2,572
    yeah, thats pretty much what I did....I made an adjecencey list that keeps track of vertecies and the edges...the vertecies are ints, but in the file they are strings, so I have a map of string->int, and so far its working...

    thanks for the suggestions

    some entropy with that sink? entropysink.com

    there are two cardinal sins from which all others spring: Impatience and Laziness. - franz kafka

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Longest Distance - Graph Theory
    By anirban in forum Tech Board
    Replies: 5
    Last Post: 04-25-2008, 09:02 AM
  2. Graph Theory Problems
    By anirban in forum Tech Board
    Replies: 1
    Last Post: 06-26-2007, 12:14 PM
  3. error help making no sense
    By tunerfreak in forum C++ Programming
    Replies: 5
    Last Post: 04-17-2007, 07:55 PM
  4. Graph Theory
    By xds4lx in forum A Brief History of Cprogramming.com
    Replies: 6
    Last Post: 12-17-2002, 11:58 AM
  5. FYI: Graph theory book for download
    By Shiro in forum A Brief History of Cprogramming.com
    Replies: 1
    Last Post: 07-20-2002, 10:03 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21