[JaJaBin]

Dado un grafo, al hallar su árbol de expansión mínimo mediante Prim o Kruskal, ¿cómo recorrer ese árbol en preorden?

¿Puedo hacerlo directamente con las aristas obtenidas en los métodos mencionados, o debo realizar una búsqueda en profundidad/anchura sí o sí?

[pierrot]

Hola.

No entiendo la pregunta. ¿Puedes detallarla un poco más?

Saludos.

[JaJaBin]

Hola.

No entiendo la pregunta. ¿Puedes detallarla un poco más?

Saludos.

Yo tengo un grafo ponderado G, y sobre el debo hallar el árbol de expansión de peso mínimo. Para ello utilizo el algoritmo de Prim o Kruskal...

Luego, debo escribir el árbol generado como un árbol con raíz para recorrerlo en preorden.

¿Cómo escribo el árbol de expansión como uno con raíz es mi pregunta?

[pierrot]

Yo tengo un grafo ponderado G, y sobre el debo hallar el árbol de expansión de peso mínimo. Para ello utilizo el algoritmo de Prim o Kruskal...

Sí. Asumo que G es conexo y no dirigido.

Luego, debo escribir el árbol generado como un árbol con raíz para recorrerlo en preorden.

Cómo escribo el árbol de expansión como uno con raíz es mi pregunta.

Sigo sin entenderte. Un árbol es un grafo conexo, no dirigido y que no tiene ciclos. Cualquier árbol puede ser visto como un árbol con raíz. Basta seleccionar uno de sus nodos, llamarle raíz, y considerar que todos los nodos adyacentes son sus hijos (los que se encolarían primero en una recorrida BFS).

El nodo que se elige como raíz dependerá de las particularidades de cada problema.

¿En qué contexto te surge esta pregunta?

[JaJaBin]

Te dejo un grafo y lo usamos como ejemplo



Generemos el árbol desde el vértice A, que quedaría así:




¿Cómo sería mi árbol T tomando A como raíz? ¿Simplemente el que se me generó ahí? (Viéndolo de costado, claro).

[pierrot]

¿Cómo sería mi árbol T tomando A como raíz? ¿Simplemente el que se me generó ahí? (Viéndolo de costado, claro).

Sí, pero convengamos que el concepto de "árbol con raíz" es más bien informático, donde se está usando dicho grafo como herramienta de modelado de un problema real. Como dije antes, cualquier árbol puede ser considerado un árbol con raíz, y la elección del nodo raíz responderá a las exigencias de cada problema. Dices que luego recorrerás el árbol en preorden. Bien. ¿Con qué fin? ¿Qué representan los nodos? ¿Qué representan las aristas, con sus respectivos pesos?

PD. He modificado tu mensaje. Recuerda que debes subir las imágenes como archivos adjuntos. No se permite referenciar imágenes alojadas en servidores externos al foro.

[JaJaBin]

¿Cómo sería mi árbol T tomando A como raíz? ¿Simplemente el que se me generó ahí? (Viéndolo de costado, claro).

Sí, pero convengamos que el concepto de "árbol con raíz" es más bien informático, donde se está usando dicho grafo como herramienta de modelado de un problema real. Como dije antes, cualquier árbol puede ser considerado un árbol con raíz, y la elección del nodo raíz responderá a las exigencias de cada problema. Dices que luego recorrerás el árbol en preorden. Bien. ¿Con qué fin? ¿Qué representan los nodos? ¿Qué representan las aristas, con sus respectivos pesos?

PD. He modificado tu mensaje. Recuerda que debes subir las imágenes como archivos adjuntos. No se permite referenciar imágenes alojadas en servidores externos al foro.

Ésa era mi duda. Puedo generar el árbol de distintas maneras dependiendo de la raíz que tome. Luego realizo una búsqueda en profundidad.