Help with Minimum Spanning Tree

This is a discussion on Help with Minimum Spanning Tree within the C++ Programming forums, part of the General Programming Boards category; I've got a majority of this assignment finished, except I'm having an terrible time figuring out how to implement prim's ...

  1. #1
    Registered User
    Join Date
    Sep 2010
    Posts
    1

    Help with Minimum Spanning Tree

    I've got a majority of this assignment finished, except I'm having an terrible time figuring out how to implement prim's algorithm. I understand it on paper fine and can work it out by hand, coding it is proving difficult though. I've spent quite a few days on this and this is a last ditch effort by posting here.

    I'm taking an adjacency matrix from file and creating a minimal spanning tree from it.
    lets just say

    0 2 4 -1 -1
    2 0 4 6 -1
    4 4 0 6 4
    -1 6 6 0 4
    -1 -1 4 4 0

    for our purposes here
    the -1's represent infinity, because the nodes arent connected in that case.

    User gets to pick the starting vertex, so I know that will be the first node in my tree. lets say that vertex happened to be 3. since it's stored as a 2d array, we go down that third row because vertex is 3 and find the smallest distance, which it should find 5 is the smallest right. now from there, you have the third, or the fifth column to find the next smallest item from, because we're now connected to the 5th row. Am I explaining it too unclear?

    I can't seem to figure out how to get it to properly comb through all of those
    YouTube - Prim's algorithm displays it wonderfully visually, that's kind of what i'm trying to recreate.

    Code:
      for (j=0; j<=n; j++)
        {
             int smallestWeight = 100;
             for (i=1; i<=n; i++)
             {
                  if (tree[i])
                     { 
                       if((weight[vertex][i] < smallestWeight) && (weight[vertex][i]>0))
                       {
                          smallestWeight=weight[vertex][i];
                          tree[i]=1;
                       }
                     }
             }
             mst[vertex][i]=smallestWeight;
             mst[i][vertex]=smallestWeight;
             
             
        }
    Guidance in the right direction would be fantastic if someone could help.

  2. #2
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,533
    A couple of observations.

    > for (j=0; j<=n; j++)
    To access an array of n elements, you normally write i < n
    Unless you have unusual array declarations, this looks a lot like an array overrun.

    > if (tree[i])
    If tree[i] starts as false, then the only place where this is set to true is INSIDE the test to see if it is true to begin with.
    Unreachable code perhaps?
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Updated a Minimum Spanning Tree in O(V) time?
    By scp89 in forum C Programming
    Replies: 3
    Last Post: 05-07-2009, 02:02 PM
  2. Interpreter.c
    By moussa in forum C Programming
    Replies: 4
    Last Post: 05-28-2008, 05:59 PM
  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, 09:33 AM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 10:45 PM

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