维基百科宽度优先搜索的伪码:如果"n与u相邻“，那么n的父母怎么可能是u？

Question

在研究广度优先搜索算法时，我遇到了以下伪代码：

 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)

我的问题是关于第19行(n.parent = u)：

如果"n是相邻的 to u“，那么n的父母怎么会是u？

Answer 1

根据定义，父母是其子女的邻接者，如果没有连接，他们就不会是孩子。但这不是为了这个。父指针是完全独立于图的结构的东西，它是您正在构建的新东西，它可以跟踪节点最初到达的位置。