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:
- be the vertex
V
a point of interest; by definition, V
is in the range of V
, therefore it belongs to a related component
- 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
- 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())));
Hello ana, you need to post part of the code so the community can help you, try to write something! we will help you
– Luiz Augusto
Hi @Luizaugusto, you think this method does what I want?
– ana lopes
sorry for the delay, but I believe that yes, it is returning some error ?
– Luiz Augusto
@analopes, is your graph directed or not directed? If you are not used to these terms: if there is a connection between the stations
A--B
, then there is necessarily the connectionB--A
? Or there are cases where there isA--B
but there is noB--A
?– Jefferson Quesado
@Jeffersonquesado is not directed
– ana lopes