Imagine:
A two dimensional plane (a desert for example) on the plane there are several points (oasis'es) and all of the coordinates are known.
I need to find a way to make each oasis accessible from each other oasis, but using the least amount of roadway. For example, to get from oasis C to oasis F, I may have to go via B, D and E to get there. In other words its a minimum spanning tree i am looking for.
I need a way to detect if any new roads are created, do they make any circular paths or circuits.I have included a picture for illustration. The green road is not allowed because it would create a circuit of C-B-D-E-F-C. Roads are initially added in order of length, smallest first, so the blue roads are correct and are built in this order...
E-G
B-D
A-C
E-D
B-F
B-C
E-F any roads after this one will result in a circuit.
I need an algorithm to detect new circuits each time a road is built (as detailed as possible hopefully, but pseudo code would be nice)
First version of completed program goes to the person with the answer!
Reply With Quote