Computer Science Canada

Prim's algorithm
Author:  Panphobia [ Thu Dec 19, 2013 6:20 am ]
Post subject:  Prim's algorithm
Hello everyone again!
So I am working on a problem involving a minimum spanning tree, so I tried coding prim's algorithm for this very reason, but it doesn't seem to give me the correct answer.
I am currently using this pseudo code for my algorithm.
1. Initialize a tree with a single vertex, chosen arbitrarily from the graph.
2. Grow the tree by one edge: Of the edges that connect the tree to vertices not yet in the tree, find the minimum-weight edge, and transfer it to the tree.
3. Repeat step 2 (until all vertices are in the tree).
What could be wrong with my algorithm at the moment?
Java:
public static int[][] prim(int[][]network,int A){
        int[][]newNet=new int[40][40];
        boolean[]visited=new boolean[40];
        Arrays.fill(visited, false);
        int start=A;
        while(!visited[start]){
            int min = 999999;
            int end = 0;
            for(int i=0;i<40;++i){
                if(network[start][i]==0)continue;
                if(network[start][i]<min){
                    min = network[start][i];
                    end=i;
                }
            }
            visited[start]=true;
            start = end;
        }
        return newNet;
    }
Author:  Dreadnought [ Thu Dec 19, 2013 2:34 pm ]
Post subject:  Re: Prim's algorithm
So it seems that you are starting at one vertex, finding an edge adjacent to it of minimum weight, adding this edge to your tree then repeating the procedure on the other endpoint of this added edge.

Assuming I got this right, what happens for this graph

code:
    A
     o               Start at vertex A
   /   \             edge AB has weight 1
  /     \            edge BC has weight 3
 o-------o           edge AC has weight 2
B         C

If I understand your algorithm correctly, you will get a spanning tree with edges joining A to B and B to C (total weight 4) when the answer should have total weight 3.
Author:  Panphobia [ Thu Dec 19, 2013 3:50 pm ]
Post subject:  RE:Prim\'s algorithm
Hm, so how am I following the pseudo code wrong?
Author:  Dreadnought [ Thu Dec 19, 2013 5:04 pm ]
Post subject:  Re: Prim's algorithm
Upon further inspection your pseudo code might have another couple problems, you don't seem to avoid edges joining two vertices already in the tree and your condition for termination asks that start be visited which means you need to have a loop (or add an edge twice). It also means that your pseudo code won't do what I said it would above (sorry...).

Using my example graph above
code:
-- Begin --
start = A
min = 99999
end = Null
visited = {A : false, B : false, C : false}

-- start is not visited, we find the edge incident to start with the lowest cost --
start = A
min = 1
end = B
visited = {A : false, B : false, C : false}

-- Add edge AB to tree and set A to visited --
start = B
min = 99999
end = Null
visited = {A : true, B : false, C : false}

-- start is not visited, we find the edge incident to start with the lowest cost --
start = B
min = 1
end = A
visited = {A : true, B : false, C : false}

-- Add edge AB to tree (again) and set B to visited --

-- start is visited, return tree (single edge joining A to B) --


What you want to be doing is checking all edges that have one end in your tree and the other end outside your tree and, out of those, pick the edge with smallest weight and add it to the tree. When there are no more such edges, you know that your tree is maximal (by inclusion).
Author:  Panphobia [ Thu Dec 19, 2013 5:10 pm ]
Post subject:  RE:Prim\'s algorithm
The pseudo code I got off of wikipedia, so maybe I copied it wrong, or a less likely possibility is that wikipedia got it wrong. But anyway I will try to implement your method.
Author:  Dreadnought [ Thu Dec 19, 2013 5:21 pm ]
Post subject:  Re: Prim's algorithm
Not sure where you found the pseudo code (did a bit of searching for Prim's algorithm on Wikipedia) but what I wrote at the end of my last post is the basic idea of Prim's algorithm.

Good luck Smile
Author:  Panphobia [ Thu Dec 19, 2013 6:55 pm ]
Post subject:  RE:Prim\'s algorithm
Ok, ok I understand, prim's algorithm is like a modified Dijkstra's algorithm.

:


You can syndicate this boards posts using the file backend.php or view the topic map using sitemap.php.

Terms of Use | Privacy Policy