data structures - usos - gráfico: ¿cuáles son las desventajas si sustituyo cada lista vinculada en la lista de adyacencias por una tabla hash?

tablas hash y arboles binarios

Question

En CLRS, el impuesto 22.1-8 (soy autoaprendizaje, no en ninguna universidad)

Supongamos que en lugar de una lista vinculada, cada entrada de matriz Adj [u] es una tabla hash que contiene los vértices v para los cuales (u, v) ∈ E. Si todas las búsquedas de bordes son igualmente probables, ¿cuál es el tiempo esperado para determinar si una ¿El borde está en la gráfica? ¿Qué desventajas tiene este esquema? Sugiera una estructura de datos alternativa para cada lista de bordes que resuelva estos problemas. ¿Su alternativa tiene desventajas en comparación con la tabla hash?

Por lo tanto, si sustituyo cada lista vinculada por tabla hash, hay las siguientes preguntas:

1. ¿Cuál es el tiempo esperado para determinar si un borde está en el gráfico?
2. ¿Cuales son las desventajas?
3. Sugiera una estructura de datos alternativa para cada lista de bordes que resuelva estos problemas
4. ¿Su alternativa tiene desventajas en comparación con la tabla hash?

Tengo las siguientes respuestas parciales:

1. Pienso que el tiempo esperado es O (1), porque solo hago un Hashtable t = Adj [u], luego devuelvo t.get (v);
2. Creo que la desventaja es que Hashtable tendrá más espacios que la lista enlazada.

Para las otras dos preguntas, no puedo obtener una pista.

¿Alguien me puede dar una pista?

Answer 1

Depende de la tabla hash y de cómo maneje las colisiones, por ejemplo, suponga que en nuestra tabla hash cada entrada apunta a una lista de elementos que tienen la misma clave.

Si la distribución de los elementos es suficientemente uniforme, el costo promedio de una búsqueda depende solo del número promedio de elementos por cada lista (factor de carga). por lo tanto, el número promedio de elementos para cada lista es n / m, donde m es el tamaño de nuestra tabla hash.

1. El tiempo esperado para determinar si un borde está en el gráfico es O (n / m)
2. más espacio que la lista enlazada y más tiempo de consulta que la matriz de adyacencia. Si nuestra tabla hash admite el cambio de tamaño dinámico, necesitaríamos tiempo adicional para mover los elementos entre las tablas hash antiguas y nuevas y, de no ser así, necesitaríamos O (n) espacio para cada tabla hash para tener O (1) tiempo de consulta que resulta en espacio O (n ^ 2). también acabamos de verificar el tiempo de consulta esperado, y en el peor de los casos podemos tener tiempo de consulta como la lista enlazada (O (grado (u))), por lo que parece mejor usar la matriz de adyacencia para tener un tiempo de consulta determinista O (1) y O (n ^ 2) espacio.
3. leer más arriba
4. Sí, por ejemplo, si sabemos que cada vértice de nuestro gráfico tiene como máximo d vértices adyacentes y d menor que n, entonces, al usar la tabla hash necesitaría O (nd) espacio en lugar de O (n ^ 2) y habría esperado O ( 1) tiempo de consulta.

Answer 2

La respuesta a la pregunta 3 podría ser un árbol de búsqueda binario.

En una matriz de adyacencia, a cada vértice le sigue una matriz de elementos V. Este costo de espacio O (V) conduce a una búsqueda rápida (O (1) -tiempo) de bordes.

En una lista de adyacencia, a cada vértice le sigue una lista, que contiene solo los n vértices adyacentes. Esta forma de espacio eficiente conduce a una búsqueda lenta (O (n)).

Una tabla hash es un compromiso entre la matriz y la lista. Utiliza menos espacio que V, pero requiere el manejo de colisiones en la búsqueda.

Un árbol de búsqueda binario es otro compromiso: el costo de espacio es mínimo como el de las listas, y el costo promedio de tiempo en la búsqueda es O (lg n).

Answer 3

Las preguntas 3 y 4 son muy abiertas. Además de los pensamientos de los otros dos, un problema con la tabla hash es que no es una estructura de datos eficiente para escanear elementos desde el principio hasta el final. En un mundo real, a veces es bastante común enumerar todos los vecinos para un vértice dado (por ejemplo, BFS, DFS), y eso de alguna manera compromete el uso de una tabla hash directa.

Una posible solución para esto es encadenar los cubos existentes en la tabla hash para que formen una lista con doble enlace. Cada vez que se agregue un nuevo elemento, conéctelo al final de la lista; Cuando se elimine un elemento, elimínelo de la lista y corrija la relación de enlace en consecuencia. Cuando quiera hacer un escaneo general, simplemente repase esta lista.

El inconveniente de esta estrategia, por supuesto, es más espacio. Hay una sobrecarga de dos punteros por elemento. Además, la adición / eliminación de un elemento lleva más tiempo para construir / arreglar la relación de enlace.

No estoy demasiado preocupado por las colisiones. La tabla hash de un vértice almacena sus vecinos, cada uno de los cuales es único. Si su clave es única, no hay posibilidad de colisión.