Thread: Appropriate container for prim's algorithm

  1. #1
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654

    Appropriate container for prim's algorithm

    I have a question.
    I'm working on an implementation on Prim's algorithm currently, and I need an appropriate container.
    Since I need to find the lowest cost edge, I wanted a container that could effectively sort the data to keep them in a sorted order, so that I could take the first edge, check if it's one I can use, and if not, pick the next lowest weight, and so on.

    I have thought about priority queues. Only, they lack iterators. That means I would have to pop the front, check it, then push it if it doesn't fit what I need. And then it appear in the front again.

    A binary heap wouldn't necessarily keep the items in sorted order, nor do I think they have iterators, so that wouldn't do either. Or if it did, it would probably be a little more complicated.

    Another option, I suppose, would be some queue I could sort of a linked list to which I apply mergesort, since from my experiements, it's pretty fast on sorted data.

    Those are my thoughts.
    Now I want to know if anyone else has any ideas or thoughts.
    Thanks.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  2. #2
    Registered User
    Join Date
    Oct 2008
    Posts
    1,262
    wikipedia is quite good for this:
    Prim's algorithm - Wikipedia, the free encyclopedia

  3. #3
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    For learning how the algorithm works, yes, but not for implementing it.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  4. #4
    Registered User
    Join Date
    Oct 2008
    Posts
    1,262
    Did you read the link I sent? It goes directly to time complexity per data structure. That's what you want, isn't it?

  5. #5
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    Yes, I saw that. But if that was enough, I wouldn't be asking.
    I have been to Wikipedia, oh I don't know how many times, looking at this algorithm and others.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  6. #6
    Registered User
    Join Date
    Oct 2008
    Posts
    1,262
    Well, I don't know if how I always did it is optimal... But I'd store all edges per vertex in a vector. Then pick a random vertex and insert all edges in a set, sorted by length. Then I'd pick the shortest edge by selecting the first one in the set that doesn't have a vector in the spanning tree on both ends (simply a vector of bools per vertex, set to false to begin with). Then I'd insert all edges from the new vertex into the set and continue like that.

    In the programming contests this solution was always fast enough, though I doubt it's optimal.

  7. #7
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    I did solve this some two days ago. Probably not optimal.
    Still, I will be going back to some work requiring the use of a graph and finding the shortest path between two nodes, so I'll come back to this algorithm a little later, and I'll look at optimizing it a little more.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Algorithm help and multiple container ownership question...
    By dudeomanodude in forum C++ Programming
    Replies: 1
    Last Post: 05-17-2008, 10:06 PM
  2. Linked List Queue Implementation help
    By Kenogu Labz in forum C++ Programming
    Replies: 8
    Last Post: 09-21-2005, 10:14 AM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM