比较不同的对象

Question

最近有人问我这个面试问题。

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

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，请尝试反向比较。检查C是否在D的adjList中，如果是则D>C，如果您无法从两端到达目标，则return？说明找不到任何关系。这种方法看起来正确吗？有没有更好的方法？

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

Answer 1

你是对的，给定的集合关系形成了一个图。仔细观察，您会发现这样创建的图实际上是一个 有向无环图 (DAG)（正如@RalfKleberhoff 在评论中指出的那样）。这使得检查关系 (compareing) 变得更加容易。为了保持一致性，我将假设 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 中的一个节点，其所有后代（children、grandchildren 等）都小于（<）它。同样，一个节点的所有祖先（parents、grandparents 等）都大于（>）它。

比较不同的对象

Compare different objects

algorithm

graph-algorithm

说明