← Volver a los ejercicios

Cuántas flechas llegan

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.

1. El grafo

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.

2. Llene los grados de entrada

VérticeG[u]Grado de entrada

3. Cuántas veces se ejecuta la suma

¿Cuántas veces se ejecuta la línea 6 sobre este grafo?

4. Ejecute el conteo

entrada: –
Paso 0 de 0
La flecha que se está contando queda azul en el dibujo.

5. Fuentes y sumideros

¿Cuáles vértices de este grafo son fuentes?

6. Para llevarse

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?