Gráfico: componentes fuertemente conectados

¿Hay alguna forma rápida de determinar el tamaño del componente más grande fuertemente conectado en un gráfico?

Quiero decir, el enfoque obvio significaría determinar cada SCC (podría hacerse usando dos llamadas DFS , supongo) y luego recorrerlas y tomar el máximo.

Estoy bastante seguro de que tiene que haber un enfoque mejor si solo necesito tener el tamaño de ese componente y solo el más grande, pero no puedo pensar en una buena solución. ¿Algunas ideas?

Gracias.

Déjame responder tu pregunta con otra pregunta:
¿Cómo se puede determinar qué valor en un set es el más grande sin examinar todos los valores?

En primer lugar, podría usar el algorithm de Tarjan que solo necesita un DFS en lugar de dos. Si entiende el algorithm claramente, los SCC forman un DAG y este algo los encuentra en el order topológico inverso. Entonces, si tiene una idea del gráfico (como una representación visual) y si sabe que ocurren SCC relativamente grandes al final del DAG, entonces podría detener el algorithm una vez que se encuentren los primeros SCC.

    Intereting Posts