4.3.4. Algoritmos sobre grafos dirigidos.

Grafos dirigidos acíclicos

procedure OrdenTopológico(G: grafo; var num_top: array [1..N] of integer);

var C: Cola(nodo);

contador: integer;

v, w: nodo;

begin

Anula (C); contador:= 1;

for cada nodo v do

if GradoEnt[v] = 0 then

InsertaCola(v, C);

while not EsVacíaCola(C) do begin

v:= FrenteCola(C);

SuprimirCola(C);

num_top[v]:= contador;

contador:= contador + 1;

for cada w adyacente a v do begin

GradoEnt[w]:= GradoEnt[w]-1;

if GradoEnt[w] = 0 then

InsertaCola(v, C);

end; {for}

end; {while}

end; {Si contador<n ? existe un ciclo }

• Ejemplo.

• ¿Cuál es el orden de complejidad del algoritmo, con matrices y listas de adyacencia?

Diapositiva anterior

Diapositiva siguiente

Ir a la primera diapositiva

Ver versión gráfica