Clausura transitiva en grafos no dirigidos

propuesto por josejuan

Dado un grafo no dirigido, obtener la clausura transitiva, es decir, el conjunto de conjuntos de nodos conectados.

Enunciado
La clausura transitiva viene a decir que "los amigos de mis amigos son mis amigos", así, en un grafo, si los nodos a y b están conectados (indicado normalmente como (a, b)) y también lo están (b, c) entonces, en la clausura transitiva también lo estarán (a, c).

Se trata de escribir una función tal que, dado un grafo de entrada no dirigido, devuelva otro grafo no dirigido que sea la clausura transitiva del primero.

No hay restricción en cuanto a la representación del grafo, pero un ejemplo podría ser:

** ENTRADA
[(1, 2), (1, 3), (4, 5), (5, 6)]

** SALIDA (clausura transitiva del grafo de entrada)
[(1, 2), (1, 3), (2, 3), (4, 5), (4, 6), (5, 6)]


NOTA: una clausura C de un elemento X es tal (informalmente) que la clausura de C es siempre él mismo (es decir C). Es decir (informalmente), la condición transitiva debe aplicarse sucesivamente mientras se pueda. Lo que quiere decir que "los amigos de los amigos de los amigos ... de mis amigos son mis amigos".

Ver todo el enunciado

Preguntas sobre el desafío
  • ¿Jose Juan puedes poner un ejemplo de entrada?

    ¡Claro!

Plantea tu pregunta

3 Soluciones

Dar mi solución

Dar mi solución