1

在 PHP 工作 2 年后，我将返回 Java。对不起，如果这看起来很愚蠢：

这是代码（图的深度优先遍历）：

public List<List<Edge>> paths = new ArrayList<>();

public void traverse(Edge edge, List<Edge> currentPath){
    String vertex = graph.getEdgeTarget(edge);
    if(edge!=null) currentPath.add(edge);
    if(vertex=="TARGET_VERTEX"){
        System.out.println(currentPath);  // prints fine

        paths.add(currentPath); // elements are empty at end of reccursion

        if(edge!=null) currentPath.remove(edge);
        return;
    }
    for(Edge e : graph.outgoingEdgesOf(vertex)){
        traverse(e, currentPath);
    }
    if(edge!=null) path.remove(edge);
}

public void search(){
    //graph is initalized, vertices and edges are added

    for(Edge e : graph.outgoingEdgesOf("START_VERTEX")){
        traverse(e, new ArrayList<Edge>());
    }
    System.out.println("############################");
    System.out.println(paths);
    System.out.println(paths.size());
}

有人可以解释为什么递归结束时paths有空元素，以及如何使其包含我需要的路径吗？
似乎通过引用传递让我成为一个问题......

ArrayList有一个浅clone()方法，它不会复制元素（根据 JavaDoc）。
我是否需要创建一个临时变量来手动复制currentPath（遍历值）？

我仍然对Java中的值传递和引用传递有点困惑，在PHP中使用传递引用（&variable.）很容易区分。

编辑所以我不会抱怨字符串比较

4

4 回答 4

1

您正在从路径中添加和删除。看来是做错了，你可以试试调试应用程序。

Java 是按值传递的。这意味着像这样的方法

public void myMethod(MyObject instance) {...}

接收对 的引用值的副本instance。如果在你做的方法内

instance.setField(newValue);

那么您正在访问您传递的同一对象，因为引用具有相同的值。但是，如果您在方法中执行此操作

instance = new MyObject(newValue);

那么用于调用该方法的对象将保持不变。发生这种情况是因为您更改了副本中的引用值，而不是原始值

你可以在javadude看到更详细的解释。

最后，您应该使用 .equals 方法而不是使用 == 来比较字符串和其他对象。这个答案应该可以帮助你。

对您的代码进行鸟瞰，我会更正它（没有尝试）：通过为字符串常量创建常量。

//These two lines, minor improvements
public static final String TARGETV= "TARGET_VERTEX";
public static final String STARTV= "START_VERTEX";

改变

if(vertex=="TARGET_VERTEX"){

至

  if(vertex.equals(TARGETV)){

关于打印路径变量，System.out.println 将打印一个字符串，您正在传递一个对象（边缘列表列表）。每个对象都有一个toString()方法，当需要将对象作为字符串时，该方法会自动调用。如文档中所述，默认情况下：

Object 类的 toString 方法返回一个字符串，该字符串由对象作为其实例的类的名称、at 符号字符“@”和对象哈希码的无符号十六进制表示形式组成。

因此，您可以：

创建一个新类（在内部实现 aList<List<Edge>>并覆盖该toString()方法），或者您可以实现如下方法：

public static String printPath(List<List<Edge>> paths){
   StringBuffer sb = new StringBuffer();
   for(List<Edge> le : paths){
     for(Edge e: le){
         sb.append(le); //or similar method to print edges to String
      }
   }
   return sb.toString();

}

而不是：

System.out.println(paths);

做这个：

System.out.println(printPaths(paths));
于 2013-07-23T17:35:57.750 回答
1

该行if(edge!=null) currentPath.remove(edge);删除了您的List.

currentPath正如递归的那样，这很可能会导致您的问题。

在不相关的问题上，您正在比较Stringwith==而不是 using equals，这是不好的做法。（有关更多解释，请参见此处）。

于 2013-07-23T17:25:27.657 回答
1

这两行导致问题：

      paths.add(currentPath);
      currentPath.remove(edge);

当您添加currentPath到 时paths，它会添加 的引用currentPath。最后，currentPath是空的，因此paths留下了空引用。

为避免此问题，请创建一个副本currentPath并将副本添加到paths.

同时更新以下行：

 if(vertex=="TARGET_VERTEX"){

作为

  if("TARGET_VERTEX".equals(vertex)){

使用正确的字符串相等检查并避免 NullPointerException。

如果您想在检查时忽略大小写，请使用equalsIgnoreCase()方法。

于 2013-07-23T17:25:54.357 回答
0

您需要知道的第一件事是对象不是 Java 中的值。Java 中唯一的类型是原始类型和引用类型，因此 Java 中唯一的值是原始类型和引用。“引用”是指向对象的指针。paths, currentPath,edge等在你的代码中都是引用。元素 ofpaths和 ofcurrentPath也是引用。当你分配或传递一个引用时，你会得到另一个指向同一个对象的引用。一个新对象基本上只能在你这样做的时候创建new ...。

因此，从这一点来看，正在发生的事情应该变得更加明显。在代码中创建边列表的唯一位置是在search()函数中，当它调用traverse()函数时。该traverse()函数不包含任何对象创建表达式。因此，在所有递归和所有这些中，它都在使用和修改同一个列表对象。每次调用都会traverse()添加然后删除一个元素。所以在递归结束时，列表中将没有元素。这是您添加到其引用的同一个列表paths，因此您当然会在最后看到对空列表的引用paths。

你说你在 PHP 工作过。在 PHP5 中，对象以同样的方式工作——对象不是 PHP 中的值，它们只能通过指向对象的指针来操作。但是，PHP 中的数组（不是对象）是不同的；PHP 中的数组是值，因此在赋值或传递时，数组会被复制。

于 2013-07-25T21:54:37.897 回答