Teniendo una lista de habitaciones con sus conexiones entre sí, ¿cómo encuentro grupos de habitaciones aisladas?

Estoy tratando de crear un pequeño roguelike y fui tan lejos como al azar generando habitaciones y corredores. Cada habitación es un objeto instanciado y contiene una lista de las otras habitaciones conectadas por un pasillo.

Puedo seleccionar habitaciones que no están conectadas, pero ¿cómo puedo saber las habitaciones que están conectadas entre sí pero no con la mayoría de los demás, formando una isla?

Para ilustrar mejor el problema aquí es una imagen de la consola en un nivel empantanado. Las habitaciones 5 y 6 están conectadas solo entre sí. ¿Qué algoritmo puedo usar para detectar eso?

Comience con una lista completa de habitaciones. Elige una sala de partida. Navega desde esa habitación a todas las habitaciones conectadas. Para cada habitación que visita, quitarlo de la lista de salas y añadirlo a una lista A . Una vez que usted ha visitado todas las conexiones, las habitaciones restantes en la lista no están conectados a la sala de partida o de cualquiera de las habitaciones en la lista A .

Luego puede continuar seleccionando una habitación de lo que queda de la lista completa y navegando nuevamente. Esta vez añadiendo a la lista B . Continúe este proceso hasta que no tenga más habitaciones en la lista original. Ahora tiene listas de todos los conjuntos de habitaciones conectadas.

Problemas como este se adaptan fácilmente a los problemas de la teoría de grafos. Por ejemplo, el problema que ha descrito anteriormente se relaciona directamente con la conectividad .

Su colección de habitaciones es esencialmente un gráfico, y su problema se reduce a encontrar los componentes conectados ("islas") en ese gráfico.

Una manera simple de encontrar componentes conectados es hacer BFS (búsqueda de amplitud) desde cada vértice. Hacer BFS desde un vértice A te dará todos los vértices en el componente conectado al que pertenece el vértice A.

Entonces, básicamente, comienza con un vértice arbitrario, realiza un BFS y marca cada vértice encontrado como miembro de la primera "isla". Luego pasa al siguiente vértice sin marcar y vuelve a hacer un BFS, esta vez el etiquetado encontró vértices como miembros de la segunda "isla", y así sucesivamente.

Puedes imaginar las habitaciones como vértices en un gráfico dirigido . Al hacerlo, podrá aplicar algoritmos bien conocidos para resolver su problema.

El algoritmo de Dijkstra , por ejemplo, produce un árbol de ruta más corto para un vértice inicial dado en un gráfico. Este árbol contendrá todos los vértices alcanzables desde el punto de partida. Luego puede deducir que los vértices que no están presentes en el árbol son parte de otras islas. Puede aplicar el algoritmo a estos vértices para obtener árboles que representen cada isla.