1

我正在尝试编写一个算法来确定图形是否连接。我认为我的代码几乎是正确的，尽管我不断收到 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）。在开始访问看起来像这样：[假假假假假假]，所以没有节点被访问。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，但我不知道该怎么做 :)

4

3 回答 3

2

您发现这很难追踪的原因是您的图形类中的所有可变状态。特别是你有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()调用有效 - 因为在这种情况下您没有重置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);
        }
    }
}

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

于 2011-02-20T12:18:23.120 回答
1

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

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 )正在检查它们何时应该相同？)。

于 2011-02-20T12:11:57.133 回答
0

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

现在以两种方式识别节点

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

哦哦。现在，您必须确定，每个 String 表示在节点数组中都有一个索引。（必须有两个标识的一对一映射。）

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

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

于 2011-02-20T11:44:19.683 回答