Почему я получаю StackOverFlowError при попытке DFS этого графика?

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

Узлы являются строками!посещенные и узлы имеют одинаковую длину.Вот почему я могу использовать node.indexOf (blabla) для посещаемого массива.

UPDATE2:

Вот как выглядит график:

Уверен, проблема в том, что после N3 алгоритм зацикливается после N3, потому что он не понимает, что N1 уже был посещен.Я действительно не понимаю, почему это происходит!

UPDATE3

Строка имеет разные имена и не имеет дубликатов .. так, например, indexOf (node.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() вызов, потому что в этом случае вы не сбрасывали 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 , возвращающем что-то дурацкое, либо в индексах, используемых с посещения (в какой-то момент посещение [in] = true отмечает какой-либо другой индекс как посещенный, кроме , если (посещенный [ind] == false) проверяет, когда они должны совпадать?).

Answer 3

Настоящая проблема в том, что вы пытаетесь представить узел строкой. Делая это, вы должны хранить дочерние элементы узла в другом месте, listOfChildren. Вам также нужно отслеживать, кого вы посетили, boolean[] visited.

Узел теперь идентифицируется двумя способами

1. listOfChildren использует строковое представление "node1","node2",...
2. посещения [] использует индекс, индекс в 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;
}

Строка или индекс не нужны! Просто позвольте узлу быть узлом.