search

jorgealonsomar / TFGII-Quiz-Grafos

Trabajo de Fin de Grado. Grafos.
1 stars 0 forks source link

Error en Prim #43

Closed jjrodriguez closed 9 years ago

jjrodriguez commented 9 years ago

Pregunta del Algoritmo de Prim

Aplica el algoritmo de Prim sobre el grafo dado, tomando como origen el nodo A. En caso de poderse seleccionar más de un nodo, los nodos se deben escoger en orden alfabético. Indica cuáles de los siguientes arcos pertenecen al árbol de expansión resultante. (semilla: 650040705436673618344830759)

B-F (Pertenece) A-C (No pertenece) A-D (Pertenece) E-B (No pertenece) C-F (No pertenece)

A B C D E F A 0 8 0 5 0 8 B 8 0 3 0 0 4 C 0 3 0 3 0 5 D 5 0 3 0 0 5 E 0 0 0 0 0 0 F 8 4 5 5 0 0

A: B (8), D (5), F (8) B: A (8), C (3), F (4) C: B (3), D (3), F (5) D: A (5), C (3), F (5) E F: A (8), B (4), C (5), D (5)

El grafo generado no es conexo. El algoritmo de Prim (y el de Kruskal) solo se pueden aplicar sobre grafos conexos.

jorgealonsomar commented 9 years ago

El fallo está arreglado: El arco que faltaba para que fuera un grafo conexo sí se estaba generando, pero, al generar para ese arco un valor entre 1 y 10, se estaba usando Random.nextInt(10), lo que en realidad daba valores entre 0 y 9. Esto causaba que algunos arcos, como éste, se generaran con valor 0, por lo que era como si no existieran.