4.3.4. Algoritmos sobre grafos dirigidos.
Grafos dirigidos acíclicos
Recorrido en orden topológico: es un tipo de recorrido aplicable solamente a GDAs. Un vértice sólo se visita después de haber sido visitados todos sus predecesores en el grafo.
Este recorrido da lugar a una ordenación topológica: a cada nodo se le asigna un número num_top(v), tal que si existe una arista <i, j> entonces num_top(i) < num_top(j). En general puede existir más de un orden válido.
Ejemplo. El orden: Cimientos, Paredes, Techo, Jardín, Comprar ventanas, Fachada, es una posible ordenación topológica del grafo de tareas. En una expresión aritmética, el orden topológico a la inversa, es el orden para evaluar el resultado total de la expresión.
Implementación del recorrido en orden topológico.
1. Calcular los grados de entrada de todos los nodos.
2. Buscar un nodo v con grado de entrada 0 (es decir sin predecesores, si no hay ninguno es porque existe un ciclo). Marcarlo como visitado.
3. Para todos los nodos adyacentes a v, decrementar en 1 su grado de entrada.
4. Repetir los pasos 2 y 3 hasta haber visitado todos los nodos.