Ejercicio grafos

[martinpint]

Prerrequisitos

(Marcar colocando una X entre los corchetes los ítems que ya hiciste, así: "[X]")

• Leí las reglas del foro (https://github.com/IIC2233/Syllabus/wiki/3.-Reglas-del-foro-(issues)).
• Busqué en las issues si ya preguntaron mi duda y no encontré nada parecido (https://github.com/IIC2233/syllabus/issues).
• De ser necesario, colocaré código simple que permita explicar mi problema o duda.

Duda

Hola buenas, en el ejercicio que está adjunto no entiendo bien el enunciado y tampoco la forma de resolver el ejercicio. Entiendo como funciona la matriz de adyacencia, pero no lo que nos piden.
Según la pauta, la respuesta en la E.

[3rdPix]

Hola @martinpint !

En este ejercicio te están entregando un grafo dirigido a través de su matriz de adyacencia. Si lo visualizas, tendrás algo como lo siguiente:

Lo que te están pidiendo es que a partir de este grafo, crees nuevas aristas que conecten todos los nodos entre los que se puede llegar. Es decir, si a partir de un nodo A, es posible llegar a un nodo X (a través de cualquier camino de cualquier largo), entonces debes crear una arista "atajo" que conecte directamente A con X.

Luego, la forma de abordar este ejercicio es revisar nodo a nodo si es que puede llegar a todos los demás. Aquí te muestro un pseudocódigo que hace referencia a este proceso.

grafo: Grafo = ...
def se_puede_llegar(nodo_inicial: Nodo, nodo_final: Nodo) -> bool: ...

for nodo_de_partida in grafo.nodos:
    for nodo_de_llegada in grafo.nodos:
        if se_puede_llegar(nodo_de_partida, nodo_de_llegada):
            grafo.crear_arista(nodo_de_partida, nodo_de_llegada)

Si haces este proceso para el grafo entregado en la matriz, notarás que las conexiones que debes agregar son justamente

• Nodo 3 $\rightarrow$ Nodo 1
• Nodo 3 $\rightarrow$ Nodo 3
• Nodo 2 $\rightarrow$ Nodo 2

De modo que el grafo quedaría:

Y la matriz de adyacencia será la alternativa (E):

matriz_final: list[list[int]] = [
    [0, 0, 0],
    [1, 1, 1],
    [1, 1, 1]]

[martinpint]

Hola, creo que entiendo un poco mejor.
Entonces no es que pidan conectar todos los nodos? por qué yo pensaba que la opción correcta era la C, ya que conectaba todos los grafos tanto "de ida" como "de vuelta", pero por lo que entiendo, si empiezo en el nodo 1 del el grafo original, no puedo ir ni a 3 ni a 2, por lo que no debo conectar directamente a 1 ni con 2 ni con 3 en el nuevo grafo. Está bien esa lógica?

[3rdPix]

Correcto, debes fijarte en el enunciado. No tiene un significado oculto (ni lo tendrán las preguntas en el examen). Te dice "conectar X con Y si hay algún camino que los una"... luego, debes hacerte la pregunta:

• ¿Hay algún camino que una Nodo 1 con Nodo 2? No
• ¿Hay algún camino que una Nodo 3 con Nodo 1? Sí
• etc... (para todos los nodos con todos los nodos)

Un ejercicio en que te pidan conectar todos los nodos sin más no tendría mucha ciencia, solo debes llenar la matriz de adyancencia para hacer grafo completo:

matriz_grafo_completo: list[list[int]] = [
    [1, 1, 1],
    [1, 1, 1],
    [1, 1, 1]]

[martinpint]

Ahhh claro, ahora caché bien. Muchas gracias.