维基百科用于广度优先搜索的伪代码：如果“ n与u相邻”，n的父母怎么可能是u？

问题描述

研究算法，我遇到了以下伪代码：

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)

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

My question is regarding line 19 (n.parent = u):

如果 n是相邻，n的 parent 怎么可能是u strong>到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.

这篇关于维基百科用于广度优先搜索的伪代码：如果“ n与u相邻”，n的父母怎么可能是u？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！