El grado de salida de un vértice se lee de un vistazo: es el largo de su lista. El de entrada no está en ninguna parte y hay que contarlo recorriendo las listas de los demás. Aquí se llena a mano primero y después se ejecuta el código de la clase.
Siete vértices y ocho flechas, en lista de adyacencia. Este grafo no está en las diapositivas.
Entrada: la lista de adyacencia
G. Salida: la lista entrada, donde
entrada[v] es cuántas flechas llegan a v.
| Vértice | G[u] | Grado de entrada |
|---|
Sin solución aquí. Escriba
grados_de_salida(G) y diga por qué cuesta Θ(n) mientras que
grados_de_entrada(G) cuesta Θ(n + m). Después, sobre matriz
de adyacencia: ¿cuánto cuesta cada uno de los dos?