查找链接链的头部

Question

使用lodash，我创建了一个数组对，每个对都代表链接的源和目标。因此，对于一个链接给定路径，我有：

[ [a, b], [a, c], [d, c] ] 

这是一个给定的第一个元素是在链中的第一个环节。 我原本想将这些对映射到键/值映射对象中，然后通过键和/或值来查找头部。

简化算法：

keys.contains(a) || values.contains(a) 

如果任一为真（不包括对本身，天然地），然后它不是头。 因此，从第一对开始，keys.contains（a）|| values.contains（a）返回true，所以它不是头部，而keys.contains（b）|| values.contains（b）返回false - 所以它必须是头部。

问题：我无法将这些对映射到一个对象中，因为可能存在互相重叠的键/值重复项。

即上面的例子中，生成的目标将是：

{ 
    a: c, 
    d: c 
} 

我知道我可以通过他们循环，但是我不愿意做这么多的循环，除非我不得不...

更高效的解决方案的任何想法？

Answer 1

我假设来源是关键，目的地是价值。有向图的根源是那些不作为值出现的键。 （叶子：反之亦然）。

a将是一个根，以及d。 b和c不是。你的情况应该是keys.contains(a) && !values.contains(a)。

如果对象指向对方（[ [a, b], [b, a] ]）或某物指向自己（[ [a, a] ]），您可能根本没有根。

现在，如果您消除了自引用，则可以收集键和值。为了得到根，你遍历键并测试它们是否不是一个值。为了获得叶子，你迭代这些值并测试它们是否不是关键。

HTH，但我不知道我是否正确理解您的问题。