algorithm - 比较不同的对象

Question

我最近被问到这个面试问题。

假设您有一个 set(K a, K b) 和 compare(K a, K b) 接口(interface)。 例如:

set(A,B) means A>B
set(B,C) means B>C
set(B,D) means B>D

Now 
compare(A,B) returns '>'
compare(B,A) returns '<'
compare(A,C) returns >
compare(C,D) returns ?

我的回答:我最初认为它代表一个图，我可以构建一个图并进行拓扑排序，但这没有帮助。

下一个方法:- 使用 set 方法创建邻接表。 例如:

A->B
B->C,D
C->E
D->F

比较(A，B)的逻辑..从 A 开始做 DFS 并检查你能达到目标。例如:使用 DFS 比较 (A,C) A->B->C

现在比较(C,D) - 如果无法从 C 的 adjList 到达 D，请尝试反向比较。检查D的adjList中是否有C，如果有则D>C，如果两端都达不到目标则返回？说明找不到任何关系。这种方法看起来正确吗？有没有更好的方法？

编辑:我们可以使用 Floyd Warshall 算法吗？ 例如:创建一个额外的 bool 矩阵并添加 >、<、=、？基于传递性的符号？

Answer 1

你是对的，给定的集合关系形成了一个图。仔细观察，您会发现这样创建的图实际上是一个有向无环图 (DAG)(正如@RalfKleberhoff 在评论中指出的那样)。这使得检查关系(compare ing)变得更加容易。为了保持一致性，我假设 set(A, B) => A > B => B is a child of A (确切地说，您的邻接表是如何生成的)。

一旦我们有了 DAG，我们的 compare(X, Y)算法简单如下:

compare(X, Y):
    if X is descendant of Y: // i.e. a DFS/BFS starting from Y will successfully find X
        return '<'
    if Y is descendant of X:
        return '>'
    else:
        return '?'

说明

由于我们构建 DAG 的方式，对于 DAG 中的节点，其所有后代(子代、孙代等)都小于 (<) 它。同样，一个节点的所有祖先( parent 、祖 parent 等)都大于(>)它。