Encontrar todos los subgrafos desconectados en un gráfico

Tengo un gráfico que contiene un número desconocido de subgráficos desconectados. ¿Cuál es un buen algoritmo (o biblioteca de Java) para encontrarlos a todos?

Creo que lo que estás buscando generalmente se llama un Relleno de inundación. Depende de usted si atraviesa el gráfico a través de un BFS o un DFS.

Básicamente, toma un nodo sin etiquetar (también conocido como sin color) y le asigna una nueva etiqueta. Asigna la misma etiqueta a todos los nodos adyacentes a ese, y así sucesivamente a todos los nodos a los que se puede acceder desde ese nodo.

Cuando no se pueden etiquetar más nodos accesibles, comienza de nuevo eligiendo otro nodo sin etiquetar. Tenga en cuenta que el hecho de que este nuevo nodo no esté etiquetado implica que no es accesible desde nuestro nodo anterior y, por lo tanto, se encuentra en un componente desconectado diferente.

Cuando no haya más nodos sin etiquetar, la cantidad de etiquetas distintas que tuvo que usar es la cantidad de componentes del gráfico. La etiqueta de cada nodo le indica qué nodo forma parte de qué componente.

No es una implementación de Java, pero tal vez sea útil para alguien, así es como se hace en Python:

import networkx as nx
g = nx.Graph()
# add nodes/edges to graph

d = list(nx.connected_components(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 asumo que esta es una pregunta de tarea o una pregunta de autoeducación, por lo que no voy a dar una respuesta directa.

Los dos algoritmos básicos para detectar la conectividad de un gráfico son Primera búsqueda en profundidad y Búsqueda primero en amplitud. Esos son realmente los 2 puntos de partida que desea ver. Ambos lo llevarán a la solución, pero de diferentes maneras, y es difícil discutir cuál es “mejor” sin considerar algunos aspectos bastante profundos del problema. Pero sigamos adelante.

Como mencioné antes, omitió algunos detalles importantes y mencionaré algunas posibilidades aquí.

¿Tu gráfico es 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 abordar 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 está bien. 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 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 libros, lo cual es bueno. 🙂 El siguiente paso sería el contar de gráficos, literalmente el número de ellos, y que el libro tampoco es tan malo. Por último, 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 (así que el tipo de retorno sería una lista de gráficos, supongo, con una invariante implícita de que cada gráfico está conectado). Ninguno de estos diferentes tipos de resultados requeriría un algoritmo diferente, pero ciertamente requieren un enfoque diferente al libro.

Todo esto puede parecer una exageración ridícula 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 suspenso, tenga en cuenta que nada de esto toca el tiempo de ejecución o el uso de la memoria. 🙂 -Agor

JGraphT es una buena biblioteca de gráficos 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.

Supongo que desea encontrar todos los componentes (fuertemente) conectados. Para eso puedes usar Algoritmo de Tarjan (una variante de DFS)

¿Qué pasa con una búsqueda en amplitud para encontrar todos los nodos conectados? Una vez que tenga la lista de nodos conectados, reste esta lista de la lista de todos los nodos. Terminas con una lista de nodos desconectados

Probablemente debería haber encontrado un algoritmo estándar (Wikipedia tiene algunas sugerencias), pero se me ocurrió esto por mi cuenta y funcionó bien para mis propósitos. Mi implementación de C# tarda un par de segundos en procesar un gráfico con 40 000 nodos y 44 000 bordes para encontrar 160 subgráficos y 20 000 nodos desconectados. Usé un HashSet para almacenar cada grupo de subgráficos, por lo que la membresía del grupo de prueba es aproximadamente O(1), y el algoritmo general se convierte en O(E*C) donde E es el número de aristas y C es el número de componentes conectados en el gráfico . Wikipedia menciona un algoritmo O(N), lineal en el número de nodos, por lo que estoy seguro de que el mío no es lo más eficiente posible, pero fue bastante rápido para mi aplicación. (Editar: también estoy pasando por alto el costo de fusionar grupos, así que no ponga demasiado peso en mi análisis de complejidad).

Lógica:

For each edge A->B
  If A is in a group and B is not, add B to group A
  If A is not in a group and B is, add A to group B
  If A and B are in different groups, merge the groups
  If neither A or B is in a group, create new group containing A and B

Pseudocódigo:

graph = {nodes, edges}
groups = {}
foreach edge A->B in graph.edges:
    groupA = findgroup(A)
    groupB = findgroup(B)
    if (groupA && !groupB)
        groupA.add(B)
    elif (!groupA && groupB)
        groupB.add(A)
    elif (groupA && groupB)
        if (groupA != groupB)
            groupA.union(groupB)
            groups.delete(groupB)
    else
        groups.add({A,B})

findgroup(node):
    for group in groups:
        if group.contains(node):
            return group
    return null

Tenga en cuenta que esto no capturará ningún nodo que no esté involucrado en los bordes. Para mis propósitos particulares, esto estuvo bien. Si desea obtener todos los grupos de un solo nodo, puede hacer un paso final:

foreach node in graph.nodes:
    group = findgroup(node)
    if !group:
        groups.add({node})