创建对象的依赖树

Question

我正在开发一个项目，需要识别对象之间的依赖关系并按顺序解析这些对象。

输入

1. obj1 >> obj3（对象3依赖于对象1）
2. obj2 >> obj4（对象4依赖于对象2）
3. obj1 >> obj2（对象2依赖于对象1）

我将此依赖信息作为 json 的输入获取。我必须检查这些依赖关系并确定应该首先创建哪些对象。然后从那里开始创建其他对象

所以在上面的例子中依赖顺序会是这样的。所有这些对象都有一个字符串 Id。因此，在输出中包含该 Id 就足够了

输出

obj1 >> obj2 >> obj3 >> obj4

我可以先创建 obj1 然后创建 obj2 等

解决此类问题的有效算法应该是什么

所以我目前的方法是将这些依赖信息添加到一个映射中，并迭代这个映射并找到顺序

Map<Object, List<Obj>>

在场景 obj1 >> obj2 中

地图的键 - obj1 值 - obj2

我认为这不是一个有效的方法

Answer 1

您可以从入度为 0 的所有节点开始运行拓扑排序。

// input is Map that maps EVERY node to a list of nodes that depend on it
List<String> getOrder(Map<String, List<String>> dependents) {
    Map<String, Integer> in = new HashMap<>();
    for (var lst : dependents.values())
        for (var d : lst)
            in.merge(d, 1, Integer::sum);
    Queue<String> queue = new ArrayDeque<>();
    for (var o : dependents.keySet())
        if (!in.containsKey(o))
            queue.add(o);
    List<String> order = new ArrayList<>();
    while (!queue.isEmpty()) {
        var curr = queue.poll();
        order.add(curr);
        for (var next : dependents.get(curr))
            if (in.merge(next, -1, Integer::sum) == 0)
                queue.add(next);
    }
    return order;
}