2 replies to this topic

[XZhang]

Hi,

Consider the following:

-I have a big two dimensional array of points (a square lattice).
-Each edge between points is assigned a value between 0 and 1 at random, call it the 'value' of the edge
-I start at some point in the middle. I consider the edges connecting to all adjacent vertices, and whichever has the least value, I add the point it joins to to my set.
-I repeat this process.

So at each step, I need to check the values of all the edges from points in my existing set, except those that joint to another vertex in my set.

I would like this to be as quick as possible... what would be the best way?

Just checking the edges from EVERY point in the existing set becomes very slow as the number of points in the set increases, nor should it be neccessary, considering that at each step we're only adding one more point, which will not affect the permissible adjacent points for most of the points in the graph...

[bobdark]

Please provide some additional clarifications:
1) What does represent array[i][j]? Some point? If so then what fields does the point have? Or maybe it represents the value of the edge between points i and j?
2)How do we know the value of an edge connecting two points??
3)Do you have memory limitations? Upper bound for memory complexity?
4)Do you want code or an algorithm?

[WingedPanther]

Are you just trying to find the minimal spanning tree?