javascript - 穿过充满物体的物体

Question

我通过 php 从数据库获取数据，并通过以下方式将 php 数组转换为 javascript:

var dbarrayjs = <?php echo json_encode($dbarrayphp);?>;

这样，js 输出一个对象，其中数据库的每条记录本身就是一个对象。记录(我的数据库的一行)由 2 个字符串组成。其中一个字符串是一个数字列表，用“,”分隔，需要通过string.split更改为数组。另一个字符串是一个简单的数字。这句话的意思是描述树状系统的前身。一位数字字符串是一个节点，多数字字符串包含其所有直接父节点。一个特殊的标准是，所有 parent 都需要通过才能确认 child 。

我需要一种方法来遍历这个系统，并检查我是否可以到达这棵树中的每个元素，或者是否有一个元素由于错误的前任选择而无法到达。一个简单的例子是这样的:

编辑:2017 年 3 月 21 日 - 我正在寻找顶排序算法，但当时并不知道。

Answer 1

这是图论中的一个基本算法。您有一个有向图:连接仅朝一个方向进行。如果您有给定的根节点，则搜索相当简单:对根树进行完整遍历(深度优先或 breadth-first )。然后查看是否已命中所有节点。

你的问题描述有点模糊:你只需要检测是否有丢失的节点？需要鉴定一下吗？是否真的只有一个节点缺失？根据这些详细信息，您的实现的会计可能需要做更多的工作。

例如，如果您所要做的就是检测是否有任何丢失的节点，只需在搜索中访问节点时对节点进行计数即可。如果最终计数小于数据库中的节点数，则说明缺少一些节点。

如果您必须识别丢失的节点，那么您必须跟踪您访问过的节点。然后，您需要另一个代码块来提取图表的所有节点，报告那些不在您的“访问”列表中的节点。