实现具有多个 parents 和 children 的图形

Question

我需要实现一个 tree-like 数据结构，其中每个节点有多个 parents 和 children，因此有多个根。

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

节点不会以 children 开头，但任何现有节点都可以获得另一个 child 节点以及任意数量的其他 parent 节点

Answer 1

我能够创建 Node class 和 Graph class。我给每个 Node 一个 List<Node> 他们的 parent 和 child 节点。

每个 Node 跟踪自己的直接 children 和 parents。

节点实现

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 class 仅用于跟踪图的根。根只是一个没有 parent 的 Node。可以针对您的特定用例调整每种方法的范围。 class 旨在通过更具体的 class 进行扩展，其中包括处理特定数据类型的方法。

图表实现：

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);
        }
    }
}

添加带有 parents 的新 Node 时，Graph class 获取 parents 并将 Node 添加为那些 parent 中的 child，因此 parent 节点知道它们有 child 个节点。

实现具有多个 parents 和 children 的图形

Implementing a graph with multiple parents and children

java

graph-theory

directed-acyclic-graphs

data-structures