Implementación del algoritmo de ordenación topológica Java

La codificación del algoritmo depende de la representación del grafo, con matriz de adyacencia
o listas de adyacencia. Si el grafo tiene relativamente pocos arcos, (poco denso), la matriz de
adyacencia tiene muchos ceros (es una matriz esparcida), y entonces el grafo se representa con
listas de adyacencia. En el caso de grafos dirigidos densos se prefiere, por eficiencia, la matriz
de adyacencia. Con independencia de la representación, se utiliza una Cola para almacenar los
vértices con grado de entrada 0.
La siguiente codificación representa un grafo representado con listas de adyacencia (clase
GrafoAdcia); los vértices de la ordenación topológica se escriben por pantalla, y se guardan
en el vector T[].

import TipoCola.*;
import ListaGenerica.*;
// Método que devuelve el grado de entrada del vértice v .
// Se suponen los vértices numerados de 0 a n-1
public static int gradoEntrada(GrafoAdcia g, int v) throws Exception
{
int cuenta = 0;
for (int origen = 0; origen < g.numeroDeVertices(); origen++)
{
if (g.adyacente(origen, v)) // arco incidente a v
cuenta++;
}
return cuenta;
}
// Método para obtener una ordenación topológica.
// Muestra los vértices que pasan a formar parte de la
// ordenación, y se guardan en T[]
public static
void ordenTopologica(GrafoAdcia g, int[]T) throws Exception
{
int []arcosInciden;

int v, w, nvert;
ColaLista cola = new ColaLista();
nvert = g.numeroDeVertices();
arcosInciden = new int[nvert];
// grado de entrada de cada vértice
for (v = 0; v < nvert; v++)
arcosInciden[v] = gradoEntrada(g, v);
System.out.println("\n Ordenación topológica ");
for (v = 0; v < nvert; v++)
if (arcosInciden[v] == 0)
cola.insertar(new Integer(v));
VerticeAdy [] vs = new VerticeAdy[nvert];
vs = g.vertices();
while (!cola.colaVacia())
{
Integer a;
Arco elemento;
ListaIterador itl;
int j = 0;
a = (Integer)cola.quitar();
w = a.intValue();
System.out.print(" " + vs[w].toString());
T[j++] = w;

itl = new ListaIterador(g.listaAdyc(w)); // iterador de lista
// decrementa grado entrada de vértices adyacentes
while ((elemento = (Arco)itl.siguiente())!= null)
{
v = elemento.getDestino();
arcosInciden[v]--;
if (arcosInciden[v] == 0)
cola.insertar(new Integer(v));
}
}
}