java - 在类似图形的对象中查找循环

Question

我正在实现某种类图对象，我现在将对其进行描述。

我有以下对象:

节点 - 包含两个 double (纬度、经度)和两个弧(边)。MeetingPointNode 扩展节点 - 包含两个 double (纬度、经度)和八个弧。Arc - 包含一个节点列表(一些常规的一些交汇点)。环 - 包含弧列表。 (基本上它看起来像多边形)。

我有以下问题:我需要从一个随机的汇合点开始并迭代，直到我回到同一个汇合点或者我进入死胡同(我只迭代汇合点而忽略常规节点)。这是我试图实现该目标的实现:

public void findRing(Node ringHead, Node current, List<Arc> arcs, Ring foundRing) {
        if (current == ringHead) {
            foundRing = new Ring();
            foundRing.setArcs(arcs);
            return;
        }

        for (int i = 0; i < 8; i++) {
           Arc currentArc = current.getArcs()[i];
           if (currentArc == null) {
                return;
           }

           arcs.add(currentArc);
           currentArc.setIsUsed(true);
           for (Node n : currentArc.getListOfNodes()) {
               if (n.getClass() != MeetingPointNode.class)
                   continue;
               findRing(ringHead, n, arcs, foundRing);

           }
           if (foundRing == null) {
              currentArc.setIsUsed(false);
              arcs.remove(current);
           }
       }
       return;
}

我将按以下格式调用该方法:findRing(head, headNext /* the next meetingPoint from head*/, new ArrayList<Arc>(), null);

我很乐意得到任何帮助。

Answer 1

您可以使用 LinkedHashSet 并在访问节点时存储它们。当您找到第一个重复项时，您就有了一个 Ring。

LinkedHashSet 保持元素插入集合的顺序，因此您可以轻松导出 Ring 路径。