时间戳

首页 > 解决方案 > 递归方法中 ArrayList 的行为

java - 递归方法中 ArrayList 的行为

问题描述

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

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

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

输出应为：
ABCD
ACD

我已经编写了下面的代码以及额外的输出来检查发生了什么，因为它不能正常工作。下面代码的输出是：

上一个向量：SA
向量历史大小：1
下一个向量：AB
上一个向量：AB
向量历史大小：2
下一个向量：BC
上一个向量：BC
向量历史大小：3
下一个向量：CD
上一个向量：CD
向量历史大小：4
下一个向量: DA
Looped - ABCDA
ABCDA
ABC
AB
向量历史大小：4
下一个向量：AC
Looped - AC
AC

如您所见，while 循环的第二次迭代的最后 4 行是错误的，因为向量历史大小应该为 1（仅限 SA），并且“C”之前不应该被访问，但不知何故，第一个向量历史的 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;
        }
    }

}

标签： javarecursionarraylistreference

解决方案

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

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

你的程序看起来很奇怪；）你用向量的 equal 做的魔法并不好，因为你实际上不能比较两个相等的对象。例如，您的代码 AB 与 AB 不同（事实并非如此）。因此，对于您去过的地方，您不需要向量而是点。所以这里有一个稍微修改过的程序，只是为了说明我的意思。它仍然远非完美：

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); 为了这项工作。请用大写字母命名您的课程。

推荐阅读