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 回答