We want to run BFS on very large graphs, where we can't store the whole graph upfront, but where only the neighbours of a vertex are shown at a time, using some form of unique identifier. How can we modify BFS to handle such situations $($used for example for crawling the Internet$),$ while still maintaining efficiency?

We want to run BFS on very large graphs, where we can't store the whole graph upfront, but where only the neighbours of a vertex are shown at a time, using some form of unique identifier. How can we modify BFS to handle such situations $($used for example for crawling the Internet$),$ while still maintaining efficiency?

One just ignores whether one has already seen a vertex or not; so the memory of the algorithm just keeps the current neighbourhood in mind $($so to speak$).$

This can not be done, but BFS needs to see the whole graph from the beginning.

An appropriat dictionary is to be used, where all seen vertex$-$ids are stored. In the loop where all neighbours of a vertex are scanned, those which are already in the dictionary are ignored, while the others $($the new ones$)$ are entered into the dictionary. The objects stored in the dictionary consist of the id plus the distance$-$value and the parent$-$pointer.

One keeps a list of vertex$-$ids seen. When scanning the neighbours of a vertex, one checks in the list whether one has already seen the neighbour $($in which case the neighbour is ignored$),$ while otherwise one adds the new vertex to the list $($with information on distance and parent$).$