圆图的数据结构与算法

Question

我需要为web客户端为Data Structure和Algorithm定义Circular Data Graph。

在服务器端，数据将以2列CSV格式提供(例如发件人、接收器)。

最终输出将以JSON格式呈现并发送到web请求。

我已经看到了一些Tree的例子，可以帮助亲子关系。但在我的例子中，我有一个递归关系i.e. A Parent's grand child can also be used as a Parent；这使我在无限循环中运行时有点困难。

数据：

Sender,Receiver
A,B
A,H
B,C
B,D
D,E
E,F
F,G
G,C
H,I
H,J
J,K
K,L
L,M
M,K
L,N
N,O
N,P
P,A
N,Q

客户机可以这样呈现(我只关心Java结构)：

客户端可以请求任何节点，而我必须生成整棵树并发送响应，即A、K或N。

​

​

问题：

1. 对于这个需求，什么是最好的Data Structure？例如，喜欢Tree还是其他什么？
2. 我应该编写自己的逻辑来读取数据并在Tree中设置，还是有任何标准的算法？
3. 避免递归的最好方法是什么？

在这里，任何有用的示例都会有帮助:)

也请参阅我的工作解决方案如下。

Answer 1

我确信，在如何实现类似树的结构方面，您已经发现的树示例是正确的。在您的例子中，您有一个额外的复杂性，即递归循环可能存在，因为某些子对象将精确地引用他们的祖先之一。(对吧？)

由于这种复杂性，任何试图通过迭代每个节点的子节点遍历树的进程都会围绕这些递归连接循环，直到堆栈溢出。

在这种情况下，您不再真正地处理一棵树。从数学上讲，树被定义为无圈图。在您的例子中，您有周期，因此不是树，而是圆图。

我过去曾处理过这样的情况，我认为你可以用两种方式处理这件事。

1. 打破循环(在对象级别)，返回到树。当发生这些递归连接之一时，不要将真正的对象引用放置到祖先，而是一个存根，它指示它连接到哪个对象，而不是对象对该项的引用。
2. 请接受您有一个循环图，并确保您的代码在遍历该图时能够处理这一问题。确保与图形交互的任何客户端代码能够检测到它在递归分支中的情况，并对其进行适当处理。

IMHO选项2不是很有吸引力，因为您可能会发现很难保证约束，而且它经常会导致错误。只要您可以为树中的每个项分配一个唯一标识符，选项1就能很好地工作，尽管客户端仍然需要了解这种可能性，以便他们能够处理去耦合链接并正确地表示它(例如，在树视图UI中)。您仍然希望建模一个循环图，但是将使用树在对象级别表示它，因为它简化了代码(和表示)。

备选案文1的全部例子：

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;


public class CyclicGraphTest 
{   
    public static void main(String[] args) 
    {       
        new CyclicGraphTest().test();           
    }

    public void test()
    {
        NodeManager manager = new NodeManager();
        Node root = manager.processNode("ZZZ");
        root.add(manager.processNode("AAA"));
        manager.get("AAA").add(manager.processNode("BBB"));
        manager.get("AAA").add(manager.processNode("CCC"));
        manager.get("AAA").add(manager.processNode("DDD")); 
        manager.get("DDD").add(manager.processNode("EEE"));
        manager.get("EEE").add(manager.processNode("FFF"));
        manager.get("FFF").add(manager.processNode("AAA"));
        manager.get("AAA").add(manager.processNode("JJJ")); 
        root.add(manager.processNode("EEE"));
        GraphWalker walker = new GraphWalker(manager, root, 1);
        System.out.println(walker.printGraph());        
    }

    /**
     * Basic Node
     */
    public class Node implements Iterable<Node>
    {
        private String id;
        private List<Node> children = new ArrayList<Node>();

        public Node(String id) {            
            this.id = id;
        }

        public boolean add(Node e) {
            return children.add(e);
        }

        public String getId() {
            return id;
        }

        @Override
        public Iterator<Node> iterator() {          
            return children.iterator();
        }           
    }

    /**
     * Cyclical Reference
     * 
     */
    public class ReferenceNode extends Node
    {
        private String refId;

        public ReferenceNode(String id, String refId) {
            super(id);
            this.refId = refId;
        }

        @Override
        public boolean add(Node e) {
            throw new UnsupportedOperationException("Cannot add children to a reference");
        }

        public String getRefId() {
            return refId;
        }           
    }   

    /**
     * Keeps track of all our nodes. Handles creating reference nodes for existing
     * nodes.
     */
    public class NodeManager
    {
        private Map<String, Node> map = new HashMap<String, Node>();

        public Node get(String key) {
            return map.get(key);
        }

        public Node processNode(String id)
        {
            Node node = null;
            if(map.containsKey(id))
            {
                node = new ReferenceNode(getRefId(id), id);
                map.put(node.getId(), node);                
            }
            else
            {
                node = new Node(id);
                map.put(id, node);
            }
            return node;
        }

        private String getRefId(String id) {
            int i = 0;
            String refId = null;
            while(map.containsKey(refId = id + "###" + i)) { i++; }
            return refId;
        }

        public Node resolve(ReferenceNode node) {
            return map.get(node.getRefId());
        }
    }

    /**
     * Walks a tree representing a cyclical graph down to a specified level of recursion
     */
    public class GraphWalker
    {
        private NodeManager manager;
        private Node root;
        private int maxRecursiveLevel;

        public GraphWalker(NodeManager manager, Node root, int recursiveLevel) {
            super();
            this.manager = manager;
            this.root = root;
            this.maxRecursiveLevel = recursiveLevel;
        }

        public String printGraph()
        {
            return printNode(root, 0, "   ").toString();
        }

        private StringBuilder printNode(Node node, int recursionDepth, String prefix) {
            Node resolvedNode = resolveNode(node, recursionDepth);
            if(resolvedNode != node) {
                recursionDepth ++;
                node = resolvedNode;
            }
            StringBuilder sb = new StringBuilder(node.getId());
            int i = 0;
            for(Node child : node)
            {
                if(i != 0) sb.append("\n").append(prefix);
                sb.append(" -> ").append(printNode(child, recursionDepth, prefix + "       "));             
                i++;
            }
            return sb;
        }

        /**
         * Returns a resolved reference to another node for reference nodes when the 
         * recursion depth is less than the maximum allowed
         * @param node
         * @param recursionDepth
         * @return
         */
        private Node resolveNode(Node node, int recursionDepth) 
        {           
            return (node instanceof ReferenceNode) && (recursionDepth < maxRecursiveLevel) ? 
                    manager.resolve((ReferenceNode) node) : node;
        }
    }

}

Answer 2

把你的例子存储在内存中？由于您所描述的是一个图形，请看以下内容：在内存中存储图形的三种方法及其优缺点

Answer 3

使用递归，并提供一个深度参数，它告诉每个输出元素前面有多少空格。

与…有关的东西：

private final int INDENTSIZE = 4;

public void printNodes() {
    for (Node n : roots) {
        System.out.print("- " + n.getName());
        printNode(n, 1);
    }
}

private void printNode(Node n, int depth) {
    List<Node> children = n.getChildren();

    for (Node child : children) {
        printIndent(depth);
        System.out.print("- " + child.getName());
        printNode(child, depth + 1);
    }
}

private void printIndent(int depth) {
    System.out.println();
    for (int i = 0; i < depth * INDENTSIZE; i++) {
        System.out.print(" ");
    }
}

当然，您必须自己实现的getChildren()。如果你有一张地图或一棵树就不会那么难了。

但是，此示例不引入循环引用，然后将永远循环。