java - 实现具有多个 parent 和 child 的图表

Question

我需要实现一个树状数据结构，其中每个节点都有多个父节点和子节点，因此有多个根节点。

新节点将仅作为没有父节点的根节点或一个或多个父节点的子节点添加到树中。

节点不会以子节点开始，但任何现有节点都可以通过任意数量的其他父节点获得另一个子节点

Answer 1

我能够创建一个 Node类和 Graph类(class)。我给了每个 Node一个List<Node>它们的父节点和子节点。

每个Node跟踪它自己的直接 child 和 parent 。

节点实现

public class Node<T>{
    private T data;
    private List<Node<T>> parents;
    private List<Node<T>> children = new ArrayList<>();//this can be initialized because a node will not start with children
    public Node(T data){//adding a node without parents
        this.data = data;
        parents = new ArrayList<>();//make parents an empty ArrayList so other methods won't break with a null value
    }
    public Node(T data, List<Node<T>> parents){//adding a node with parents
        this.data = data;
        this.parents = parents;
    }

    //search methods
    public List<Node<T>> getChildren(){return children;}//return only direct children
    public List<Node<T>> getChildren(int level){return getChildren(new ArrayList<>(Collections.singletonList(this)),new ArrayList<>(),level);}//convenience method to find only this node's children to a certain level
    public List<Node<T>> getChildren(List<Node<T>> find, List<Node<T>> found, int level){//level can be -1 to search through all children or a positive integer to only search the first n level of children.
        if(level!=0){//setting level to -1 will never stop the search until all children have been found because level only goes down, because the level will never reach zero
            for(Node<T> node:find){//can find the children of multiple nodes
                if(node.hasChild()) {
                    for (Node<T> child : node.getChildren()) {
                        if (!found.contains(child)) {//trees can intersect, so the child may have already been found, so only add if it hasn't
                            found.add(child);
                        }
                    }
                    getChildren(node.getChildren(),found,level--);//recursively find the remaining children of the current node
                }
            }
        }
        return found;
    }
    //a method that finds parents can be implemented by modifying the getChildren() methods

    //examples of other methods that can be added
    public T getData(){return data;}
    public boolean hasChild(){return children.size()>0;}
    void addChild(Node<T> node){children.add(node);}
    void addChildren(List<Node<T>> nodes){children.addAll(nodes);}
    public List<Node<T>> getParents(){return parents;}
    public boolean hasParent(){return parents.size()>0;}
    void addParent(Node<T> node){parents.add(node);}
    void addParent(List<Node<T>> nodes){parents.addAll(nodes);}
}

Graph类仅用于跟踪图的根。根就是一个 Node没有 parent 。可以针对您的特定用例调整每种方法的范围。此类旨在通过更具体的类进行扩展，其中包含用于处理您的特定数据类型的方法。

图实现:

public class Graph<T> {
    private List<Node<T>> roots;
    protected Tree(List<Node<T>> roots){this.roots = roots;}//Graph class can be initialized with or without existing roots 
    protected Tree(){roots = new ArrayList<>();}
    public List<Node<T>> getRoots(){return roots;}
    public List<Node<T>> getAllNodes(){
        List<Node<T>> nodes = roots.get(0).getChildren(roots,new ArrayList<>(),-1);//loop through all roots with an empty list for nodes already found, because no nodes have been found yet
        nodes.addAll(roots);
        return nodes;
    }
    public void addNode(Node<T> node){
        for(Node<T> parent:node.getParents()){//for each parent node add this node as their child
            parent.addChild(node);
        }
        if(!node.hasParent())roots.add(node);
    }
    public void addNodes(List<Node<T>> nodes){
        for(Node<T> node:nodes){
            addNode(node);
        }
    }
}

添加新的 Node 时与 parent ，Graph类获取 parent 并添加 Node作为那些 parent 的 child ，所以 parent 节点知道他们有 child 节点。