Results 1 to 5 of 5

Thread: Question about Prim's Algorithm

  1. #1
    Newbie
    Joined
    Mar 2017
    From
    Philadelphia
    Posts
    5

    Question about Prim's Algorithm

    Let's say from a vertex there are two surrounding vertices. But they both have the same weight (or cost) as each other. Which do you choose?
    For example...

    Question about Prim's Algorithm-questionaboutthis.gif

    On step C, the edge going from B to E has the same weight as the edge going from A to H. Why did this example choose to go from B to C? Is there any reason? Or do we just pick one or the other in this situation?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Apr 2005
    Posts
    19,454
    Thanks
    2892

    Re: Question about Prim's Algorithm

    "Choose"? What criteria are you using to choose one of these over the others?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Nov 2013
    From
    California
    Posts
    5,919
    Thanks
    2491

    Re: Question about Prim's Algorithm

    the pseudocode I just looked at chooses the first min weight edge it finds during it's search at each step

    one could modify that to create a list of all min weight edges available per step and randomly choose one.

    If you wanted to be more clever you could do an n-step search that looks for the min weight path of n edges.

    n in this case should be very small in relation to the overall size of the graph.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Mar 2017
    From
    Philadelphia
    Posts
    5

    Re: Question about Prim's Algorithm

    Do you see the edge that connects A to H? And another one that connects from B to C. They both have the same edge weight of 8. Why did that picture connect B to C rather than A to H on the third step?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Mar 2017
    From
    Philadelphia
    Posts
    5

    Re: Question about Prim's Algorithm

    Quote Originally Posted by HallsofIvy View Post
    "Choose"? What criteria are you using to choose one of these over the others?
    Do you see the edge that connects A to H? And another one that connects from B to C. They both have the same edge weight of 8. Why did that picture connect B to C rather than A to H on the third step?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Prim's algorithm vs Kruskal algorithm
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Apr 4th 2017, 10:05 PM
  2. [SOLVED] algorithm Question
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: Dec 6th 2010, 12:30 PM
  3. Algorithm question
    Posted in the Math Topics Forum
    Replies: 8
    Last Post: Aug 5th 2009, 06:19 AM
  4. Prim's Algorithms
    Posted in the Advanced Applied Math Forum
    Replies: 0
    Last Post: Nov 13th 2007, 09:02 AM
  5. Algorithm Question
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: Sep 4th 2007, 04:29 AM

Search tags for this page

Click on a term to search for related topics.

/mathhelpforum @mathhelpforum