节点套娃问题 -(节点重复利用如何避免循环)

2021 年 12 月 23 日
本文字数：1829 字
阅读完需：约 6 分钟

问题简介：

如图，1 号节点的第二个子节点 3，是否能增加子节点 6？不能！因为 6 的子节点 2 已有子节点 3，如若增加，则导致无限套娃。

如何实现不断的添加又不产生无限套娃？

Code：

import com.alibaba.fastjson.JSON;import org.springframework.util.CollectionUtils;import java.util.*;
public class NodeCircle {    public static Map<Long, Map<Long, Integer>> nextMapMap = new HashMap<>();
    public static void main(String[] args) {        List<Node> nodes = Arrays.asList(                new Node(1L, "2,3"),                new Node(2L, "5,3"),                new Node(3L, null),                new Node(4L, null),                new Node(5L, null),                new Node(6L, "2"),                new Node(7L, "3"));        for (Node node : nodes) {            if (node.getSonIds() != null) {                String[] sonIdStrs = node.getSonIds().split(",");                for (String sonIdStr : sonIdStrs) {                    Long sonId = Long.parseLong(sonIdStr);                    Map<Long, Integer> nextMap = nextMapMap.computeIfAbsent(node.getId(), k -> new HashMap<>());                    int nextCount = nextMap.computeIfAbsent(sonId, k -> 0);                    nextCount += 1;                    nextMap.put(sonId, nextCount);                }            }        }        System.out.println(JSON.toJSONString(nextMapMap));        link(3L, 6L);        unlink(6L, 2L);        System.out.println(JSON.toJSONString(nextMapMap));        link(3L, 6L);        System.out.println(JSON.toJSONString(nextMapMap));        link(1L, 2L);        System.out.println(JSON.toJSONString(nextMapMap));    }
    public synchronized static boolean haveCircle(Long nodeId, Long linkId) {        if (nodeId.equals(linkId)) {            return true;        }        Map<Long, Integer> linkNextMap = nextMapMap.get(linkId);        if (CollectionUtils.isEmpty(linkNextMap)) {            return false;        }        Set<Long> linkNext = linkNextMap.keySet();        if (linkNext.contains(nodeId)) {            return true;        }        for (Long next : linkNext) {            if (haveCircle(nodeId, next)) {                return true;            }        }        return false;    }
    /*     * nodeId next add linkId count     */    public synchronized static void link(Long nodeId, Long linkId) {        if (haveCircle(nodeId, linkId)) {            System.out.println("have circle nodeId:" + nodeId + " linkId:" + linkId);            return;        }        Map<Long, Integer> nodeNextMap = nextMapMap.computeIfAbsent(nodeId, k -> new HashMap<>());        Integer nodeNextCount = nodeNextMap.computeIfAbsent(linkId, k -> 0);        nodeNextMap.put(linkId, nodeNextCount + 1);    }
    /*     * nodeId next reduce linkId count     */    public synchronized static void unlink(Long nodeId, Long linkId) {        Map<Long, Integer> nodeNextMap = nextMapMap.computeIfAbsent(nodeId, k -> new HashMap<>());        int nodeNextCount = nodeNextMap.computeIfAbsent(linkId, k -> 0);        if (nodeNextCount <= 1) {            nodeNextMap.remove(linkId);            if (CollectionUtils.isEmpty(nodeNextMap)) {                nextMapMap.remove(nodeId);            }        } else {            nodeNextMap.put(linkId, nodeNextCount - 1);        }    }
    public static class Node {
        public Long getId() {            return id;        }
        public String getSonIds() {            return sonIds;        }
        private final Long id;        private final String sonIds;
        public Node(Long id, String sonIds) {            this.id = id;            this.sonIds = sonIds;        }    }}