Si encuentras algún error con tu código o trabajo, recuerda probar siempre en un entorno de testing antes subir el código al trabajo final.
Solución:
gráfico denso es un gráfico en el que el número de aristas está cerca del número máximo de aristas.
Gráfico disperso es un gráfico en el que el número de aristas está cerca del número mínimo de aristas. Gráfico disperso puede ser un gráfico desconectado.
Como los nombres indican, los gráficos dispersos están escasamente conectados (p. ej., árboles). Por lo general, el número de aristas está en O(n), donde n es el número de vértices. Por lo tanto, se prefieren las listas de adyacencia, ya que requieren un espacio constante para cada borde.
Los grafos densos están densamente conectados. Aquí el número de aristas suele ser O (n ^ 2). Por lo tanto, se prefiere la matriz de adyacencia.
Para dar una comparación, supongamos que el gráfico tiene 1000 vértices.
Independientemente de si el gráfico es denso o disperso, la matriz de adyacencia requiere que se almacenen 1000^2 = 1,000,000 valores.
Si el gráfico está mínimamente conectado (es decir, es un árbol), la lista de adyacencia requiere almacenar 2997 valores. Si el gráfico está completamente conectado, requiere almacenar 3.000.000 de valores.
De Estructuras de datos y algoritmos con patrones de diseño orientados a objetos en C++, pág. 534, de Bruno P. Reiss:
De manera informal, un gráfico con relativamente pocos bordes es escaso y un gráfico con muchos bordes es denso.
Definición (Gráfico disperso): Un gráfico disperso es un gráfico G = (V, E) en el que |E| = O(|V|).
Definición (Gráfico denso) Un gráfico denso es un gráfico G = (V, E) en el que |E| = Θ(|V|2).