Check if the graph is connected

  

As the question is about non-directed graphs, I am using this as a premise in my entire answer. Everything I write applies to non-directed graphs unless you find some external reference that shows otherwise. I will not take care here to make explicit what goes for targeted graphs.

Let's start by defining what is a related component? This will serve as a basis for eventual code and also for a common denominator to get here.

A connected component is composed of one vertex and all the other vertices that it can reach. How is this done? Well, we can see this recursively:

I would particularly do the navigation to determine the reach of a vertex through a search in depth, not a search in width. Because? Because with an in-depth search I have a smaller memory spike in most cases (the opposite can happen in sparse graphs, where depth searching can take up more memory) and because it's easier to implement.

How would I do this search? Well, it depends a lot on how your graph is structured. I really like the adjacency matrix , but it does not seem to be the case. I'm going to pretend that the mapaEstacoes object has a List<Estacao> vizinhos(Estacao e) method that returns all neighbors of e . I tried to think of some way to make my code the most similar to what you posted, however, as yours is not recursive and I did not understand the use or need of the variable css , I could not.

Basically, I'm going to get all the related components of a graph. I will map these related components into sequential identifiers and map each station to a related component. Therefore, I will have a Map<Estacao, Integer> that will identify, for that station, what its related component.

The search will start by passing a vertex (representing an unrelated connected component) and the identifier of the related component. As I reach new vertices, they will certainly follow one of these two properties: (a) they are already in the connected component in question, (b) they have not yet been visited. I will indicate that a vertex has not been yet when querying the vertex map for identifier of the connected component results in null .

public static Map<Estacao, Integer> buscarComponentesConexos(GrafoMisterioso mapaEstacoes) {
    Map<Estacao, Integer> relacaoComponentesConexos = new HashMap<>();
    int idComponenteConexoInedito = 0;

    for (Estacao v: mapaEstacoes.vertices()) {
        if (relacaoComponentesConexos.get(v) == null) {
            determinaComponenteConexo(v, idComponenteConexoInedito, mapaEstacoes, relacaoComponentesConexos);
            idComponenteConexoInedito++;
        }
    }
    return relacaoComponentesConexos;
}

private static void determinaComponenteConexo(Estacao v, int idComponenteConexo, GrafoMisterioso mapaEstacoes, Map<Estacao, Integer> relacaoComponentesConexos) {
    // se eu cheguei aqui, então devo marcar o vértice passado como pertencente ao componente conexo
    relacaoComponentesConexos.put(v, idComponenteConexo);

    // percorre os vizinhos...
    for (Estacao u: mapaEstacoes.vizinhos(v)) {
        // se o vizinho u ainda não foi visitado, visite-o
        if (relacaoComponentesConexos.get(u) == null) {
            determinaComponenteConexo(u, idComponenteConexo, mapaEstacoes, relacaoComponentesConexos);
        }
    }
}

With this, from a graph, we can determine for all its points which are its related components. Not exactly the related components, but almost ...

A graph is said to be connected if it contains only a single connected component. How can I find out? Well, let's use stream to check for any index greater than zero?

Map<Estacao, Integer> relacaoComponenteConexo = buscarComponentesConexos(mapaEstacoes);
OptionalInt qualquerOutro = relacaoComponenteConexo.values().stream().mapToInt(Integer::intValue).filter(v -> v > 0).findAny(); // estou considerando que o sequencial 0 sempre é usado para o primeiro componente conexo
boolean grafoConexo = !qualquerOutro.isPresent();

What if I need to search for each related component? Well, in that case, we need to reverse the mapping. Now, should I map from an index to a list of vertices:

Map<Estacao, Integer> relacaoComponenteConexo = buscarComponentesConexos(mapaEstacoes);
Map<Integer, List<Estacao>> = relacaoComponenteConexo.entrySet().stream()
  .collect(
            Collectors.groupingBy(es -> es.getValue(),
              Collectors.mapping(Entry::getKey, Collectors.toList())));