Teniendo una gráfica acíclica dirigida (DAG, por sus siglas en inglés), nos interesa encontrar una forma en que podamos acomodar los vértices en línea recta de tal forma que la dirección de los arcos siempre apunte hacia un mismo lado. Un ejemplo de cuando se dan este tipo de gráficas, es en las materias de estudios superiores. Se tienen que tomar algunas materias antes que otras (materias seriadas), pero nunca se puede formar un ciclo (o no se podrían estudiar estas materias).
Como no hay forma en que nos podamos regresar, podemos ver a este tipo de gráfica en forma similar a un árbol. Podemos utilizar cualquier forma de recorrer un árbol para encontrar el ordenamiento topológico, pero es más conveniente utilizar una búsqueda en profundidad ya que es más fácil de implementar.
A esto se le conoce como ordenamiento topológico, ya que estamos acomodando los vértices en cierto orden, y topológico viene de Topología que es la rama de las matemáticas que estudia problemas geométricos no por la forma del objeto sino por la forma en que está conectado.
Problema ejemplo
Árbol Genealógico
El parentesco entre marcianos es bastante confuso. Ellos pueden reproducirse cuando quieran y donde quieran. Y pueden hacerlo en grupo, por lo que un marciano puede tener sólo un padre o quizás diez. Nadie se sorprende por tener cientos de hijos. Los marcianos están acostumbrados a esto, y para ellos es normal.
Esto puede producir situaciones vergonzosas en el Consejo Planetario. Para respetar jerarquías y no ofender a nadie, se acostumbra cederles la palabra a los marcianos ancianos primero, seguido por los adultos, después los jóvenes y así sucesivamente. Sin embargo, encontrar este orden no es una tarea trivial, ya que un descendiente no puede hablar antes que un superior. Y el problema se agrava porque un marciano no siempre conoce a todos sus padres (¡y ni se diga de sus abuelos!). Pero si por error habla primero el nieto que su, en apariencia más joven, abuelo, se forma un tremendo escándalo.
Problema
Tu tarea es escribir un programa que pueda encontrar, de una vez por todas, un orden que garantice que todos los miembros del Consejo tengan la palabra antes que cualquiera de sus descendientes.Entrada
La primera línea en la entrada estándar contiene solo un número n, 1 ≤ n ≤ 100 — la cantidad de miembros del Consejo Planetario Marciano. De acuerdo a una tradición centenaria, los miembros del Consejo están numerados de 1 a n. Además, en la entrada existen exactamente n líneas, donde la i-ésima línea contiene a la lista de hijos del i-ésimo miembro. La lista de hijos es una serie de números en orden arbitrario separados por espacios, la cual puede estar vacía. La lista (incluso si está vacía) termina con un 0.Salida
La salida estándar debe contener en una sola línea una serie de números separados por un espacio en blanco, que representa el orden en que van a tomar la palabra los miembros del Consejo. Si existen varias listas que cumplan las condiciones del problema, puedes escribir cualquiera de ellas. Siempre existirá por lo menos una de ellas.
Solución: Necesitamos que tener a los marcianos ordenados de tal forma que cualquiera de ellos hable antes que sus descendientes. Tomando a cada marciano como un vértice, y a las aristas como descendencia, tenemos que las aristas están dirigidas y no hay ciclos por la misma razón: no es posible que alguien sea ancestro de un ancestro.
Código
La declaración de variables la realizamos entre las líneas 1 y 4. La variable n indica la cantidad de vértices, i es para los ciclos y t la utilizamos para leer los vértices adyacentes. Utilizamos el arreglo vis para saber si ya visitamos determinado vértice, y m es la matriz de adyacencia.
En la función t_sort realizamos el ordenamiento topológico. Como ya habíamos mencionado, es una búsqueda en profundidad. En la línea 9 marcamos el vértice como visitado, y en las siguientes dos líneas buscamos sus vértices adyacentes. Por adyacente en este caso estamos revisando si marciano actual tiene ascendencia. Escribimos el número del vértice hasta el final para empezar desde las hojas hasta la raíz, es decir, desde quienes no tienen ascendencia (mayores) hasta quienes tienen más (menores).
Caso ejemplo
| Entrada: |
5 0 4 5 1 0 1 0 5 3 0 3 0 |
| Desarrollo: |
num[] 1 2 3 4 5 1 FALSE FALSE FALSE FALSE FALSE 2 TRUE FALSE FALSE TRUE TRUE 3 TRUE FALSE FALSE FALSE FALSE 4 FALSE FALSE TRUE FALSE TRUE 5 FALSE FALSE TRUE FALSE FALSE v 1, num[2,1]= TRUE, vis[2]= FALSE 1, num[3,1]= TRUE, vis[3]= FALSE write(2) 3, num[4,3]= TRUE, vis[4]= FALSE 4, num[2,4]= TRUE, vis[2]= TRUE write(4) 3, num[5,3]= TRUE, vis[5]= FALSE 5, num[2,5]= TRUE, vis[2]= TRUE 5, num[4,5]= TRUE, vis[4]= TRUE write(5) write(3) write(1) |
| Salida: | 2 4 5 3 1 |
Código en C
Tiempo de ejecución
| Lenguaje | Fecha | Tiempos [s] | Memoria [Kb] | |||
|---|---|---|---|---|---|---|
| Ejecución | Mejor | Mediana | Peor | |||
| Pascal | 04-May-2006 | 0.001 | 0.001 | 0.015 | 1.101 | 218 |
| C | 04-May-2006 | 0.001 | 162 | |||
Otros problemas
Valladolid:
Project Euler:
Bicoloración
