Encontrar todos los subgrafos desconectados en un gráfico

No es una implementación de Java pero quizás sea útil para alguien, aquí está cómo hacerlo en 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

Más información aquí.

Hay muchas facetas de esta pregunta que no están completamente explicadas, así que voy a dar una respuesta algo exhaustiva. A pesar de mi tendencia a publicar muros de texto. : / Tenga en cuenta también que estoy asumiendo que esta es una pregunta de tarea o pregunta de auto-educación, así que no voy a dar una respuesta directa.

Los dos algoritmos básicos para detectar la conectividad de un gráfico es Profundidad Primera Búsqueda y Amplitud Primera Búsqueda. Esos son realmente los 2 puntos de partida que quiero mirar. Ambos te llevarán a la solución, pero de diferentes maneras, y es difícil argumentar cuál es "mejor" sin considerar algunos aspectos bastante profundos del problema. Pero sigamos adelante.

Como mencioné antes, omitiste algunos detalles importantes, y tocaré algunas posibilidades aquí.

¿Su gráfico está dirigido o no dirigido? ¿y considera la conectividad en el sentido " fuerte "(en cuyo caso, vea la respuesta de oggy), o la conectividad en el sentido" débil"? Dependiendo de su respuesta, tendrá que acercarse a su algoritmo de una manera sutilmente diferente. Tenga en cuenta que, para un gráfico no dirigido, la conectividad débil y fuerte son equivalentes, por lo que es bueno. Pero usted tendrá que mantener la estructura del gráfico en mente independientemente, mientras que la implementación o la búsqueda de un algoritmo.

Además, está la cuestión de lo que quieres decir con "encontrar los subgrafos" (paráfrasis). Por lo general, la conectividad gráfica es un problema de decisión simply simplemente "hay uno conectado graph " o " hay dos o más sub-gráficos (también conocido como, está desconectado)". Tener un algoritmo para eso requiere la menor cantidad de libros, lo cual es bueno. :) El siguiente paso sería el conteo de gráficos, literalmente el número de ellos, y que la librería tampoco es tan mala. Penúltimo, es posible que desee una lista de nodos en cada sub-gráfico. Por último, es posible que desee copiar literalmente los sub-gráficos, aristas y todo (por lo que el tipo de retorno sería una lista de gráficos, supongo, con una implícita invariante que cada gráfico está conectado). Ninguno de estos diferentes tipos de resultados requeriría un algoritmo diferente, pero ciertamente requerirá un enfoque diferente a la librería.

Todo esto puede parecer una cantidad ridícula de exceso para lo que es una pregunta bastante básica, pero pensé en resaltar todos los aspectos involucrados incluso en una pregunta gráfica tan simple. Como una especie de cliffhanger, tenga en cuenta cómo nada de esto aún toca el tiempo de ejecución o el uso de memoria! :) - Agor

JGraphT es una bonita biblioteca gráfica de código abierto con licencia LGPL. Lo he usado en el pasado para tratar con gráficos y detectar ciclos dentro de los gráficos. También es bastante fácil de usar, y puede usar JGraph para visualizar los gráficos.

Asumo que desea encontrar todos los componentes (fuertemente) conectados? Para eso puedes usar El algoritmo de Tarjan (una variante de DFS)

¿Qué tal una búsqueda de amplitud para encontrar todos los nodos conectados? Una vez que tenga la lista de nodos conectados, resta esta lista de la lista de todos los nodos. Termina con una lista de nodos desconectados

Me encontré con un problema similar donde quería todos los subgrafos débilmente conectados de un gráfico dirigido. He blogueado sobre ello aquí. Usé la API JUNG y comparé dos enfoques. Mi primer enfoque podría ser utilizado como una plantilla para resolver su problema.