java - resueltos - Encontrar todos los subgrafos desconectados en un grafico
teoria de grafos libros (7)
¿Qué tal una búsqueda más amplia 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. Usted termina con una lista de nodos desconectados
Tengo un gráfico que contiene un número desconocido de subgrafos desconectados. ¿Qué es un buen algoritmo (o biblioteca de Java) para encontrarlos a todos?
Creo que lo que estás buscando se llama generalmente Flood Fill . Depende de usted si recorre el gráfico a través de un BFS o un DFS.
Básicamente tomas un nodo sin etiquetar (AKA sin color) y le asigna una etiqueta nueva. Usted asigna la misma etiqueta a todos los nodos adyacentes a esa, y así sucesivamente a todos los nodos a los que se puede acceder desde ese nodo.
Cuando no se pueden etiquetar nodos alcanzables, empiece de nuevo seleccionando otro nodo no etiquetado. Tenga en cuenta que el hecho de que este nuevo nodo no esté etiquetado implica que no es alcanzable desde nuestro nodo anterior y, por lo tanto, está en un componente desconectado diferente.
Cuando no hay más nodos sin etiqueta, la cantidad de etiquetas distintas que debe usar es la cantidad de componentes del gráfico. La etiqueta de cada nodo te dice qué nodo es parte de qué componente.
Hay muchas facetas de esta pregunta que no están completamente explicadas, así que voy a dar una respuesta algo exhaustiva. Mi tendencia a publicar paredes de texto no obstante. : / Tenga en cuenta también que estoy asumiendo que esta es una pregunta de tarea o una pregunta de autoeducación, así que no voy a dar una respuesta directa.
Los dos algoritmos básicos para detectar la conectividad de un gráfico son Primero búsqueda de profundidad y Primera búsqueda de amplitud . Esos son realmente los 2 puntos de partida que desea ver. 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é anteriormente, omitió algunos detalles importantes, y abordaré 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 agradable. Pero tendrá que tener en cuenta la estructura del gráfico independientemente, mientras implementa o encuentra un algoritmo.
Además, está la cuestión de qué quiere decir con "encontrar los subgrafos" (paráfrasis). Por lo general, la conectividad de los gráficos es un problema de decisión, simplemente "hay un gráfico conectado" o "hay dos o más subgráficos (es decir, está desconectado)". Tener un algoritmo para eso requiere la menor cantidad de trabajo de biblioteca, lo cual es bueno. :) El siguiente paso sería el recuento de gráficos, literalmente el número de ellos, y el libro de texto tampoco es tan malo. En última instancia, es posible que desee una lista de nodos en cada subgráfico. Por último, es posible que desee copiar literalmente los subgráficos, los bordes y todo (por lo que el tipo de retorno sería una lista de gráficos, supongo, con un invariante implícito que cada gráfico está conectado). Ninguno de estos diferentes tipos de resultados requeriría un algoritmo diferente, pero sin duda requerirá un enfoque diferente para el libro.
Todo esto puede parecer una ridícula cantidad de excesos para una pregunta bastante básica, pero pensé que simplemente destacaría todos los aspectos involucrados incluso en una pregunta gráfica tan simple. Como una especie de cliffhanger, ¡observa cómo aún nada de esto toca el tiempo de ejecución o el uso de la memoria! :) - Agor
No es una implementación de Java, pero tal vez sea útil para alguien, he aquí 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 here .
Supongo que quieres encontrar todos los componentes (fuertemente) conectados. Para eso puedes usar el algoritmo de Tarjan (una variante de DFS)