Studying the Breadth-first search algorithm, I encountered the following pseudo-code:
1 Breadth-First-Search(G, v):
2
3 for each node n in G:
4 n.distance = INFINITY
5 n.parent = NIL
6
7 create empty queue Q
8
9 v.distance = 0
10 Q.enqueue(v)
11
12 while Q is not empty:
13
14 u = Q.dequeue()
15
16 for each node n that is adjacent to u:
17 if n.distance == INFINITY:
18 n.distance = u.distance + 1
19 n.parent = u
20 Q.enqueue(n)
My question is regarding line 19 (n.parent = u):
How could n's parent be u if "n is adjacent to u"?
A parent is by definition adjacent to its children, they wouldn't be children without the connection. But that's not what this is about. The parent pointers are something completely separate from the structure of the graph, it's something new you're building up that keeps track of from where a node was first reached.