java - 递归方法中 ArrayList 的行为

Question

我有一个 vector 数组列表，我试图找到所有可能的不同路径(不重复相同的节点)。但是保存路径记录的 ArrayList 似乎是共享的，因此会在所有路径中泄漏。我的问题是，是否有我应该使用的替代列表类型来防止这种情况发生？谢谢。

可用路径为(A->B、B->C、C->D、D-​​>A、A->C)

首先，我决定只处理起始节点 A 的路径。

输出应该是:
ABCD
ACD

我编写了下面的代码，并附加了输出来检查发生了什么，因为它无法正常工作。下面代码的输出是:

上一个 vector :SA
vector 历史大小:1
下一个 vector :AB
上一个 vector :AB
vector 历史大小:2
下一个 vector :BC
上一个 vector :BC
vector 历史大小:3
下一个 vector :CD
上一个 vector :CD
vector 历史大小:4
下一个 vector :DA
循环 - ABCDA
ABCDA
ABC
AB
vector 历史大小:4
下一个 vector :AC
循环 - AC
交流

正如您所看到的，while 循环的第二次迭代的最后 4 行是错误的，因为 vector 历史大小应该为 1(仅限 SA)并且“C”之前不应该被访问过，但不知何故 vector 历史的 ArrayList从第一个 while 循环的递归开始就已经泄漏了。这种情况是否会发生以及有哪些替代方案？

public static void main(String[] args) {

    ArrayList<vector> vectorList = new ArrayList();
    vectorList.add(new vector("A", "B"));
    vectorList.add(new vector("B", "C"));
    vectorList.add(new vector("C", "D"));
    vectorList.add(new vector("D", "A"));
    vectorList.add(new vector("A", "C"));

    //to record vector history and initialize the start vector
    ArrayList<vector> vectorHistory = new ArrayList();

    //record the path 
    String path = "";

    //method call
    pathFinder(new vector("S", "A"), vectorHistory, vectorList, path);
}

//Recursive method. moves one node forward until there is no more nodes OR the next node is the same as a previously taken node

public static void pathFinder(vector prevVector, ArrayList<vector>  vectorHistory, ArrayList<vector> vectorList, String path) {

    vectorHistory.add(prevVector);

    //add the current node to the path
    path = path + prevVector.child;
    System.out.println("Previous vector: "+ prevVector.parent+prevVector.child);

    // search if there is a next node.  looped to search all possible paths
    while (vectorList.contains(prevVector)) {
        System.out.println("vector history size: "+ vectorHistory.size());

        //retrieve the next vector
        vector nextVector = vectorList.get(vectorList.indexOf(prevVector));
        System.out.println("Next vector: " + nextVector.parent + nextVector.child);

        //remove current node so while loop can move to another possible path
        vectorList.remove(vectorList.indexOf(prevVector));

        //check if the next node has already been visited before
        if (vectorHistory.contains(nextVector)) {
            path=path+nextVector.child;
            System.out.println("Looped - " + path);


        } else {
            pathFinder(nextVector, vectorHistory, vectorList, path);
        }
    }

    System.out.println(path);

}

/*object vector */  
public static class vector {
    String parent, child;

    public vector(String parent, String child) {
        this.parent = parent;
        this.child = child;

    }

    @Override
    public boolean equals(Object o) {

        vector x = (vector) o;
        if (x.parent.equalsIgnoreCase(child)) {
            return true;
        } else {
            return false;
        }
    }

}

Answer 1

Java 是“按值传递”的，因此它传递实际对象的引用的副本。但是使用集合时理解起来有点奇怪，因为发送的引用的副本指向与原始引用相同的内存!

因此，如果您将列表传递给方法并修改列表中的方法，它将修改原始列表。

例如:

method b(List aList){
  aList.add(new Object());
}

method c(List aList){
  aList=new ArrayList ();
  aList.add(new Object());
}


List a=new ArrayList();
b(a); -> it will add an object to a;
c(a); -> it will not add an object to a or modify it in any way

所以就你的情况来说，当你打电话时 pathFinder(nextVector, vectorHistory, vectorList, path); 您不会获得您期望的递归“堆栈”行为，因为路径查找器的后继调用会修改前一个列表。

您可以这样修改您的调用:

pathFinder(nextVector, new ArrayList<>(vectorHistory), new ArrayList<>(vectorList), path);

为了避免这个问题，但每次复制整个列表都会丢失一些额外的内存;)并且它仍然不会得到你想要的结果，因为我猜你的算法中有另一个错误。

你的程序看起来很奇怪;)你用 vector 的相等所做的魔法并不大，因为你实际上无法比较两个相等的对象。例如，您的代码 AB 与 AB 不同(事实并非如此)。因此，对于你去过的地方，你不需要 vector ，而是点。所以这里有一个稍微修改过的程序只是为了说明我的意思。它还远未达到完美:

import java.util.ArrayList;
import java.util.List;

public class MainClass {
    public static void main(String[] args) {

        List<MyVector> vectorList = new ArrayList<MyVector>();
        vectorList.add(new MyVector("A", "B"));
        vectorList.add(new MyVector("B", "C"));
        vectorList.add(new MyVector("C", "D"));
        vectorList.add(new MyVector("D", "A"));
        vectorList.add(new MyVector("A", "C"));

        List<String> pointsHistory=new ArrayList<String>();
        //to record points that have been visited
        //record the path 
        String path = "";
        //method call
        pathFinder(new MyVector(null, "A"), pointsHistory, vectorList, path);
    }

    //Recursive method. moves one node forward until there is no more nodes OR the next node is the same as a previously taken node

    public static void pathFinder(MyVector prevVector, List<String>  pointsHistory, List<MyVector> vectorList, String path) {
        pointsHistory.add(prevVector.child);
        //add the current node to the path
        path = path + prevVector.child;
        // search if there is a next node.  looped to search all possible paths -> no need to do magic with equals
        for(MyVector vector:vectorList)
            if(vector.parent.equals(prevVector.child)) {
                  System.out.println("Next vector: " + vector.parent + vector.child);
                  if (pointsHistory.contains(vector.child)) {
                    System.out.println("Result " + path);  //You get the end result here -> if we have reached a loop
                } else {
                    pointsHistory.add(vector.child);
                     pathFinder(vector, new ArrayList<>(pointsHistory), vectorList, path);
                }
            }          
    }

    /*object vector */  
    public static class MyVector {
        String parent, child;

        public MyVector(String parent, String child) {
            this.parent = parent;
            this.child = child;
        }
    }
}

这样你就会得到你想要的结果。看看我如何复制访问过的点:pathFinder(vector, new ArrayList<>(pointsHistory), vectorList, path);为了这项工作。并请用大写字母命名您的类(class)。