为什么在尝试对该图进行 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 是我开始的某个节点，节点是节点的 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 已经被访问过。我实在不明白为什么会出现这样的情况！

UPDATE3

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

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

Answer 1

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

您依靠数组 visited 来告诉您何时停止递归，但在每次递归调用时通过调用 listOfChildren 意外地重置了数组。

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

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() 调用有效 - 因为在这种情况下您没有重置 < code>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);
        }
    }
}

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

Answer 2

我根据您的更新制作了一个小测试程序，它似乎很有魅力：

public class NodeTest
{
    static ArrayList<String> nodes = new ArrayList<String>();
    boolean visited[] = {false, false, false, false, false};

    int counter = 0;

    static HashMap<String, ArrayList<String>> childMap = new HashMap<String, ArrayList<String>>();

    static
    {
        nodes.add("N0");
        nodes.add("N1");
        nodes.add("N2");
        nodes.add("N3");
        nodes.add("N4");

        //N4 --> N2 --> N3 --> N1 <-- N0
        //       ^-------------+
        ArrayList<String> list = new ArrayList<String>();
        list.add("N2");
        childMap.put("N4", list); //N4 to N2

        list = new ArrayList<String>();
        list.add("N3"); 
        childMap.put("N2", list); //N2 to N3

        list = new ArrayList<String>();
        list.add("N1");
        childMap.put("N3", list); //N3 to N1

        list = new ArrayList<String>();
        list.add("N2");
        childMap.put("N1", list); //N1 to N2

        list = new ArrayList<String>();
        list.add("N1");
        childMap.put("N0", list); //N0 to N1
    }

    @Test
    public void test()
    {
        System.out.println("Is connected = " + isConnected("N0"));
    }

    public int isConnected(String s) 
    {
        System.out.println("Handling node " + 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)
            {
                System.out.println("Recursing into child " + listOfChildren(s).get(i));
                isConnected(listOfChildren(s).get(i));
            }
            else
            {
                System.out.println("Node " + listOfChildren(s).get(i) + " has already been visited");
            }

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

    }

    public ArrayList<String> listOfChildren(String s)
    {
        return childMap.get(s);
    }

}

isConnected 方法与您的相同，我只是添加了一些用于记录的消息。输出：

Handling node N0
Recursing into child N1
Handling node N1
Recursing into child N2
Handling node N2
Recursing into child N3
Handling node N3
Node N1 has already been visited
Is connected = 0

正如预期的那样，该图未连接（它与您在问题上绘制的图相同）。如果我将起始节点更改为 N4 并将 N1 的唯一子节点更改为 N0，则算法会正确地将图识别为已连接。基于此，我想说问题要么是 listOfChildren 返回一些古怪的东西，要么是 visited 使用的索引（在某些时候，visited[in] = true 标记其他一些索引已被访问，而不是 if(visited[ind] == false) 检查它们何时应该相同？）。

Answer 3

真正的问题是，您试图用字符串表示节点。通过这样做，您必须将 Node 的子节点存储在其他地方，listOfChildren。您还需要跟踪您访问过的人，boolean[] 访问过。

现在可以通过两种方式标识节点

1. listOfChildren 使用字符串表示形式 "node1","node2",...
2. visited[] 使用索引，即 nodes 中的索引。

哦哦。现在，您必须确保每个字符串表示形式在节点数组中都只有一个索引。 （两个标识必须是一对一的映射。）

nodes.add("node");
nodes.add("node");
nodes.add("node");

return nodes.indexOf( nodes.get(2) );//what does this return? 0!

看到问题了吗？存在一个 'node' 具有三个索引，或者存在三个同名节点！

但我正在使用数组来查看节点是否已被访问！

也许这不是同一个“节点”，您是指字符串“节点”还是索引“节点”？

要解决此问题，请为节点创建一个标识，一个表示：

public class Node
{
  List<Node> children;
}

不需要字符串或索引！只要让节点成为一个节点即可。