Java有向无环图冗余节点清理：重复ID节点合并问题求助

嘿，这个问题我之前在构建DAG时遇到过一模一样的情况！核心原因其实就是Java对象引用的特性——LinkedList是引用类型，当两个节点的childList指向同一个List实例时，它们共享同一块内存空间，所以修改其中一个的子列表，另一个必然跟着变。要解决这个问题，关键就是打破引用共享，给每个节点的子列表创建独立的实例。

下面给你几种具体的实现思路，你可以根据自己的代码结构选合适的：

1. 合并时创建新的LinkedList实例复制子节点 #

最直接的方式就是在合并重复ID节点的时候，不要直接复用原有的childList，而是新建一个LinkedList，把所有需要合并的子节点都复制进去。如果需要避免子节点重复（毕竟是DAG，可能存在重复引用），还可以顺便做去重处理。

示例代码：

// 第一步：先把所有节点按ID分组，方便处理重复
Map<String, List<Node>> nodesById = new HashMap<>();
for (Node node : yourNodeSet) {
    nodesById.computeIfAbsent(node.getId(), k -> new ArrayList<>()).add(node);
}

Set<Node> finalDagNodes = new HashSet<>();
// 处理每个ID对应的节点组
for (Map.Entry<String, List<Node>> entry : nodesById.entrySet()) {
    List<Node> sameIdNodes = entry.getValue();
    // 如果只有一个节点，直接加入结果集
    if (sameIdNodes.size() == 1) {
        finalDagNodes.add(sameIdNodes.get(0));
        continue;
    }

    // 选第一个节点作为合并基准，也可以新建节点（看你的需求）
    Node mergedNode = sameIdNodes.get(0);
    // 新建LinkedList，把基准节点的子节点先加进去
    LinkedList<Node> mergedChildren = new LinkedList<>(mergedNode.getChildList());

    // 遍历其他同ID节点，合并它们的子节点
    for (int i = 1; i < sameIdNodes.size(); i++) {
        Node otherNode = sameIdNodes.get(i);
        // 按需去重：如果子节点不在合并列表里才添加
        for (Node child : otherNode.getChildList()) {
            if (!mergedChildren.contains(child)) {
                mergedChildren.add(child);
            }
        }
        // 这里还可以合并节点的其他属性，比如描述、权重之类的
    }

    // 把独立的子列表设置给合并后的节点
    mergedNode.setChildList(mergedChildren);
    finalDagNodes.add(mergedNode);
}

2. 新建Node实例完全复制属性（更安全） #

如果你的Node类没有暴露setChildList方法，或者你不想修改原有节点的状态，更稳妥的方式是创建一个全新的Node实例，把所有同ID节点的属性（包括子节点）都复制进去，子列表同样用新的LinkedList：

Set<Node> finalDagNodes = new HashSet<>();
for (Map.Entry<String, List<Node>> entry : nodesById.entrySet()) {
    List<Node> sameIdNodes = entry.getValue();
    // 新建合并后的节点
    Node mergedNode = new Node();
    mergedNode.setId(entry.getKey());
    // 复制其他属性，比如nodeName、weight等
    mergedNode.setName(sameIdNodes.get(0).getName());
    mergedNode.setWeight(sameIdNodes.get(0).getWeight());

    // 收集所有子节点并去重
    Set<Node> uniqueChildren = new LinkedHashSet<>(); // 保持顺序的同时去重
    for (Node node : sameIdNodes) {
        uniqueChildren.addAll(node.getChildList());
    }
    // 转成LinkedList设置给新节点
    mergedNode.setChildList(new LinkedList<>(uniqueChildren));

    finalDagNodes.add(mergedNode);
}

3. 额外注意：先处理子节点再处理父节点 #

如果你的DAG里子节点也存在ID重复的情况，一定要先合并子节点，再合并父节点！不然合并后的父节点可能会指向未合并的重复子节点，导致最终的DAG还是有冗余节点。可以通过拓扑排序先处理叶子节点，再往上处理父节点。

总的来说，核心就是一句话：不要让不同节点的childList指向同一个LinkedList实例，每次合并都创建新的列表，把需要的子节点复制进去，这样修改任何一个节点的子列表都不会影响其他节点了。

内容的提问来源于stack exchange，提问作者Jack Onslow