Results 1 to 1 of 1

Math Help - Prim's Algorithms

  1. #1
    Newbie Tom G's Avatar
    Joined
    Dec 2006
    Posts
    23

    Prim's Algorithms

    I'm slightly confused as i hav 2 differing answers when using two different algorithms (Kruskal and Prim)

    For the first part i have used Prim's algorithm [tabular method] for a distance matrix (see attachment) to find the minimum spanning tree for the graph.

    My answer gives me: AB,AC,DE with AB=6, AC=7 and DE=8. this gives me a total weight of 21.
    However this is where i started to get confused as i have used Kruskals algorithm in a previous question and also Prims (the non tabular method) and got different answers with AB,AC,CD,DE with a total weight of 30.

    is this possible, the reason i ask is that in my initial answer AB,AC,DE DE is not linked to the others which makes me think that i have two seperate trees and not one spanning tree. do i need the extra edge or is it enough to have all the vertexes? Thanks in advance MHF!
    Attached Files Attached Files
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Algorithms
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: October 8th 2010, 10:48 PM
  2. algorithms
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: March 16th 2010, 03:25 PM
  3. Algorithms
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: December 17th 2009, 08:11 AM
  4. Algorithms
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: December 4th 2009, 04:06 AM
  5. Algorithms
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: March 4th 2009, 12:33 PM

Search Tags


/mathhelpforum @mathhelpforum