Simulación

Dos preguntas, dos costos

Las dos operaciones básicas de un grafo:

¿Hay arista entre u y v? En la matriz, mirar una casilla. En las listas, recorrer la lista de u.
¿Cuáles son los vecinos de v? En la matriz, recorrer toda la fila de v (V casillas). En las listas, recorrer la lista de v (grado de v entradas).

Piensa en una red social con cientos de miles de usuarios y unas decenas de amigos por usuario.

En una red de 500 000 usuarios con 80 amigos cada uno, ¿cuántas casillas mira, como mucho, listar los amigos de un usuario con la matriz? ¿Y cuántas entradas recorre, como mucho, comprobar con las listas si dos usuarios concretos son amigos?Listar amigos con la matrizComprobar una amistad con las listas