Check that the graph is connected

Question

Can anyone tell me how I can implement a method that checks me if an undirected graph is connected and, if not, returns its related components?

public void connectComps(){
    ArrayList<LinkedList<Estacao>> css = new ArrayList<>();
    Map<Estacao, Boolean> visited = new HashMap<>();
    for(Estacao est : mapaEstacoes.vertices()){
        visited.put(est, false);
    }
    for(Estacao v : mapaEstacoes.vertices()){
        if(visited.getOrDefault(v, Boolean.FALSE)){
            LinkedList<Estacao> aux = GraphAlgorithms.BreadthFirstSearch(mapaEstacoes, v);
            css.add(aux);
        }
    }
}

Answer 1

Since doubt is about undirected graphs, I’m using it as a premise in my entire answer. Everything I write is valid for undirected graphs, except if you find some external reference that shows otherwise. I will not take care here to explain what goes for directed graphs.

Let’s start by defining what a connected component is? This will serve as a basis for possible code and, also, for a common denominator to those who arrive here.

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

1. be the vertex V a point of interest; by definition, V is in the range of V, therefore it belongs to a related component
2. all edges containing V and point to other vertices Ui increase the range of V, therefore all the Ui are also within range of V
3. out of each Ui through its vertices, we arrive at the Tij, that are in the range of Ui and therefore within the scope of V

I would particularly do navigation to determine the range of a vertex through a deep search, not a wide search. Why? Because with an in-depth search I have a smaller memory peak in most cases (otherwise it can happen in sparse graphs, where the in-depth search can take up more memory) and because it is easier to implement.

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

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

The search will start by passing a vertex (representing an unreleased related component) and the identifier of the related component. As I reach new vertices, they are guaranteed to follow one of these two properties: (a) they are already in the related component in question, (b) they have not yet been visited. I will indicate that a vertex has not been visited yet when the reference to the vertex map for identifier of the related 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 connected 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 that out? Well, let’s use a stream to check if there is 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 it is necessary to search for each related component? Well, in this case, we need to reverse the mapping. Now, I must 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())));