Reading maps from .map files

[alexti]

Imagine graph:
Code:

---

x-x-x-x-x-x-x-x-x-x

---

If you start your walk from any node in the middle you'll reach dead-end without passing through all the nodes, even though the graph is connected. So you need to retrace your steps to walk through all graph. I think that establishing if the graph is connected or not is O(m), where m is number of edges (neighbour connections). However it is somewhat bigger O, in sense that each operation is more costly than iterating through the node. We start from random node, mark is as "visited", select any edge outgoing from "visited" node and mark it as "travelled", mark the node it leads to as "visited" and repeat procedure selecting the next "non-travelled" edge outgoing from "visited" node. If all nodes are "visited" at the end, the graph is connected. In this method we need no more that number of edges iterations, but the most efficient implementation of it will probably involve 2 copy of list of edges and list of nodes and moving elements from one to another, which is more costly than just iterations.