java - 为什么我在尝试 DFS 这张图时得到 StackOverFlowError？

Question

我正在尝试编写一种算法来确定图形是否连通。我认为我的代码几乎是正确的，尽管我不断收到 StackOverFlowError。我个人认为因为我正在测试我的算法的图表中有一个循环，所以我的代码不理解它并且进入循环。但是我正在使用一个数组来查看是否已经访问了一个节点!所以那不应该发生!不管怎样，这是我的代码:

public int isConnected(String s) 
    {

        int in = nodes.indexOf(s);


        visited[in] = true;
        counter++;
        for(int i = 0; i < listOfChildren(s).size(); i++)
        {
            int ind = nodes.indexOf(listOfChildren(s).get(i));
            if(visited[ind] == false)
            {
                isConnected(listOfChildren(s).get(i));
            }

        }
        System.out.println(counter);
        if(counter == nodes.size())
            return 1;
        return 0;

    }

s 是我开始的某个节点，nodes 是节点的 ArrayList 并且与访问的数组具有相同的大小(在本例中为 5)。一开始访问看起来像这样:[false false false false false]，所以没有访问任何节点。 listOfChildren() 返回特定节点的子项(不是所有子项，只是与节点相邻的子项)的 ArrayList。我确信 listOfChildren() 有效，因为我对其进行了 43545454 次测试。

感谢任何帮助(如果可能，对代码进行最少的更改)。谢谢。

更新:

我的图是有向的..

我这样定义访问:

private boolean[] visited;

然后我在我的构造函数中将其中的所有内容都设置为 false 这段代码:

public void setUnvisited()
    {
        visited =  new boolean[nodes.size()];

        for(int i = 0; i < nodes.size(); i++)
        {
            visited[i] = false;
        }
    }

节点是字符串!已访问和节点具有相同的长度。这就是为什么我可以对访问的数组使用 nodes.indexOf(blabla)。

更新 2:

图表是这样的:

我确定问题出在 N3 之后，算法在 N3 之后进入循环，因为它不明白 N1 已经被访问过。我真的不明白为什么会这样!

更新 3

字符串有不同的名称并且没有重复项..所以例如 indexOf(nodes.get(2)) 给出 2 而不是 0 或其他任何东西..

问题是在访问 N3 之后算法应该停止并返回 0 或 1，但我不知道该怎么做 :)

Answer 1

您发现这很难追踪的原因是图形类中的所有可变状态。特别是你有 count和 visited , 后者被你的两种方法修改 isConnected和 setUnvisited .

你依赖于你的数组visited告诉您何时停止递归，但通过调用 listOfChildren 不小心在每次递归调用时重置数组.

解决这个问题的一种方法是 visited不是类(class)成员。这是一个对代码修改很少的解决方案:

public boolean isConnected(String s) {
    int nVisited = isConnected(s, new boolean[nodes.size()], 0);
    return nVisited == nodes.size();
}

private int isConnected(String s, boolean[] visited, int counter) 
{

    int in = nodes.indexOf(s);


    visited[in] = true;
    counter++;
    for(int i = 0; i < listOfChildren(s).size(); i++)
    {
        int ind = nodes.indexOf(listOfChildren(s).get(i));
        if(visited[ind] == false)
        {
            counter = isConnected(listOfChildren(s).get(i), visited, counter);
        }

    }
    System.out.println(counter);
    return counter;
}

自 visited和 counter不再共享，您遇到的错误消失了。这也解决了您遇到的另一个错误(但尚未注意到)，其中只有第一个 isConnected()调用有效——因为在那种情况下你没有重置visited或 counter适本地。

与上面相同的想法的更简洁的实现:

public boolean isConnected(String s) {
    Set<String> visited = new HashSet<String>();
    isConnected(s, visited);
    return visited.size() == nodes.size();
}

private void isConnected(String s, Set<String> visited) 
{
    visited.add(s);
    for (String child : listOfChildren(s)) {
        if (!visited.contains(s)) {
            isConnected(child, visited);
        }
    }
}

我实际上并没有尝试编译或运行它，所以可能存在错误，但我希望你明白了。