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

Причина, по которой вам было так трудно отследить это, заключается в том, что все изменяемое состояние в вашем классе графа. В частности, у вас есть 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);
        }
    }
}

На самом деле я не пытался компилировать или запускать это, так что могут быть ошибки, но вы поняли, я надеюсь.

Я сделал небольшую тестовую программу на основе ваших обновлений, и, похоже, она работает как шарм:

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) проверяет, когда они должны совпадать?).

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

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

1. listOfChildren использует строковое представление "node1","node2",...
2. посещенный [] использует индекс, индекс в nodes.

Ого. Теперь вы должны быть уверены, что каждое строковое представление имеет ровно один индекс в массиве узлов. (Должно быть взаимно однозначное отображение двух идентификаций.)

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

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

Видите проблему? Есть один 'node' с тремя индексами, или есть три узла с одинаковыми именами!

Но я использую массив, чтобы увидеть, был ли уже посещен узел!

Может быть, это не тот же «узел», вы имеете в виду «узел» String или «узел» индекса?

Чтобы исправить это, создайте одну идентификацию, одно представление для узла:

public class Node
{
  List<Node> children;
}

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