> @Dennis: Did you mean "Depth-First-Search" as described in your link? > I don't see why that would make a difference here, though. Either > way, my personal implementation only iterates X times and then > restarts from a new node. It simply connects two clusters if it finds > out they share a node. This way I save a lot of memory, too.
DFS or BFS does not matter much. In your setting its basically the same and both will be effective and efficient. Testing connectivity with Dijkstra forces you to have a priority queue that sucks up O(log n) time to get the next node to explore. Doing BFS, which is essentially Dijkstras algorithm with a plain FIFO queue, gives the next node in constant time. Just try it, it will always be faster. Also, if you implement it in a correct way then there won't be any clusters that have to be joined, because they already are. --Dennis _______________________________________________ Routing mailing list [email protected] http://lists.openstreetmap.org/listinfo/routing
