Pseudo Code

Lección 4 de 9 del curso Ordenamiento Topológico - Algoritmos de Grafos de Coddy.

topologicalSort(n, edges):
   build directed adjacency; compute indeg[v] for all v
   order = []
   repeat n times:
      pick = smallest v with indeg[v] == 0 (none left -> stop)
      mark pick as used (indeg[pick] = -1)
      order.add(pick)
      for nb in adj[pick]:
         indeg[nb] -= 1
   return order

indeg[v] cuenta las aristas entrantes. Solo las aristas u -> v se suman a indeg[v].
Escanear los vértices 0..n-1 y tomar el primero con grado de entrada 0 da la opción más pequeña en cada paso, por lo que el orden es determinista.
Establecer indeg[pick] = -1 es una forma sencilla de marcar un vértice como ya colocado.

Pruébalo tú mismo

Esta lección no incluye un desafío de código.

Ponte a prueba

Esta lección incluye un breve cuestionario. Empieza la lección para responderlo y registrar tu progreso.

Todas las lecciones de Ordenamiento Topológico - Algoritmos de Grafos

1Introduction

Introduction Motivation

2The Algorithm

How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)

Time and Space Complexity

3Final Challenges

Final Challenge #1 Final Challenge #2