Encontrando todos os subgrafos desconectados em um gráfico

Question

Eu tenho um gráfico que contém um número desconhecido de subgrafos desconectados. Qual é um bom algoritmo (ou biblioteca Java) para encontrar todos eles?

Answer 1

Eu acho que o que você está procurando é geralmente chamado de Preenchimento de inundação. Cabe a você se você atravessa o gráfico através de um BFS ou um DFS.

Basicamente, você pega um nó não identificado (também conhecido como colorido) e atribui uma nova etiqueta a ele. Você atribui o mesmo rótulo a todos os nós adjacentes a esse e assim por diante a todos os nós que são acessíveis a partir desse nó.

Quando nenhum nós mais acessíveis pode ser rotulado, você começa de novo escolhendo outro nó não marcado. Observe que o fato de que esse novo nó é não marcado implica que não é acessível de nosso nó anterior e, portanto, está em um componente desconectado diferente.

Quando não há mais nós não marcados, o número de rótulos distintos que você teve que usar é o número de componentes do gráfico. O rótulo para cada nó informa qual nó é parte de qual componente.

Answer 2

Não é uma implementação de Java, mas talvez seja útil para alguém, aqui está como fazê -lo em Python:

import networkx as nx
g = nx.Graph()
# add nodes/edges to graph
d = list(nx.connected_component_subgraphs(g))
# d contains disconnected subgraphs
# d[0] contains the biggest subgraph

Mais Informações aqui.

Answer 3

Existem muitas facetas dessa pergunta que não são totalmente explicadas, então vou dar uma resposta um tanto exaustiva. Não obstante minha tendência a publicar paredes de texto. :/ Observe também que estou assumindo que essa é uma pergunta de lição de casa ou pergunta de auto-educação, por isso não vou dar uma resposta direta.

Os dois algoritmos básicos para detectar a conectividade de um gráfico são Primeira pesquisa em profundidade e Primeira pesquisa em largura. Esses são realmente os 2 pontos de partida que você deseja ver. Ambos o levarão à solução, mas de maneiras diferentes, e é difícil argumentar que é "melhor" sem considerar alguns aspectos bastante detalhados do problema. Mas vamos seguir em frente.

Como mencionei antes, você deixou de fora alguns detalhes importantes e abordarei algumas possibilidades aqui.

Seu gráfico é direcionado ou não direcionado? E você considera conectividade no sentido "forte" (nesse caso, veja a resposta de Oggy) ou conectividade no sentido "fraco"? Dependendo da sua resposta, você terá que abordar seu algoritmo de uma maneira sutilmente diferente. Observe que, para um gráfico não direcionado, a conectividade fraca e forte é equivalente, então isso é bom. Mas você terá que manter em mente a estrutura do gráfico, independentemente, implementando ou encontrando um algoritmo.

Além disso, há a questão do que você quer dizer com "Encontrar os subgrafos" (paráfrase). Geralmente, a conectividade gráfica é um problema de decisão-simplesmente "existe um gráfico conectado" ou "Existem dois ou mais sub-grafos (também conhecidos como, está desconectado)". Ter um algoritmo para isso requer a menor quantidade de livros, o que é bom. :) O próximo passo seria o contar de gráficos, literalmente o número deles, e esse livro também não é tão ruim. Penultimadamente, você pode querer uma lista de nós em cada sub-gráfico. Por fim, convém copiar literalmente os sub-gráficos, bordas e tudo (para que o tipo de retorno seria uma lista de gráficos, suponho, com um invariante implícito que cada gráfico está conectado). Nenhum desses diferentes tipos de resultados exigiria um algoritmo diferente, mas vai certamente requer uma abordagem diferente da livraria.

Tudo isso pode parecer uma quantidade ridícula de exagero para o que é uma pergunta bastante básica, mas pensei em destacar todos os aspectos envolvidos, mesmo em uma pergunta gráfica tão simples. Como uma espécie de cliffhanger, observe como nada disso ainda toca no tempo de execução ou no uso da memória! :) - AGOR

Answer 4

Jgrapht é uma boa biblioteca gráfica de código aberto licenciado pela licença LGPL. Eu o usei no passado para lidar com gráficos e detectar ciclos dentro dos gráficos. Também é bastante fácil de usar, e você pode usar Jgraph Para visualizar os gráficos.

Answer 5

Suponho que você queira encontrar todos os componentes (fortemente) conectados? Para isso, você pode usar Algoritmo de Tarjan (uma variante do DFS)

Answer 6

Que tal uma primeira pesquisa em largura para encontrar todos os nós conectados? Depois de ter a lista de nós conectados, você subtrai esta lista da lista de todos os nós. Você acaba com uma lista de nós desconectados

Answer 7

Eu encontrei um problema semelhante em que queria todos os subgrafos fracamente conectados de um gráfico direcionado. Eu escrevi sobre isso aqui. Eu usei o Jung API e compare duas abordagens. Minha primeira abordagem pode ser usada como modelo para resolver seu problema.