Actually, now that I spend more than ten seconds thinking about this, I think this requires O(1) space; you only need to remember the single most recent link behind you to avoid following it again. Remembering a single break is sufficient to get you to either the next cycle or (if no more) terminate the BFS; and once you detect the next cycle you can safely remember only /its/ break since BFS will never take you back to the first cycle. Assuming streaming output (e.g. print identification of each cycle as you detect it -- including e.g. printing each node until you see the break point, which will identify each node that is part of the cycle), this is O(n) time and O(1) space, which I believe is optimal.