Wikipedia's Breadth-First Search example: How is a parentless node reached?

Question

Now that Wikipedia's pseudo-code for BFS is clear, I look further to the graphic example provided in that entry and there is one tiny detail I don't quite understand.

In the original tree, Stuttgart looks parent-less. That is, it is neither adjacent to the root (Frankfurt) nor adjacent to the the other nodes on the same row/level (Mannheim and Wurzburg):

My question is: How is it reached/traversed at all if there is no path to it from the tree's root, such that it is eventually handled properly yielding the resultant tree?

Answer 1

The problem here is that you're considering a tree what is actually a graph. In a graph the concept of father and child node doesn't hold much sense, same as the concept of "level" (unless you consider it as number of edges that separate a node from the root): for every vertex (in the most common implementations) you have a list that represents all the adjacent vertexes, list that you can iterate in DFS or BFS searches to explore the structure. Here, Stuttgart is present in the adjacency list of Nurnberg and it's reachable from there (it doesn't matter that is "up" Nurnberg, that is just a graphical representation).