维基百科的 Breadth-first 搜索伪代码：如果 "n is adjacent to u"，n 的 parent 怎么可能是你？

Question

研究Breadth-first search算法，遇到如下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)

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

如果"n is adjacent to u"，n的parent怎么可能是你？

Answer 1

A parent 根据定义与其 children 相邻，如果没有连接它们就不会是 children。但这不是本文的目的。 parent 指针是完全独立于图形结构的东西，它是您正在构建的新东西，用于跟踪首次到达节点的位置。