Graph - Каковы недостатки, если я заменю каждый связанный список в списке смежности с хеш-таблицей?

В акцизе CLRS 22.1-8 (я сам изучаю, а не в каких-либо университетах)

Предположим, что вместо связанного списка каждый массив Adj [u] является хэш-таблицу, содержащую вершины v, для которых (u, v) ∈ E. Если все кратковременные поиски одинаково вероятны, каково ожидаемое время для определить, находится ли ребро на графике? Какие недостатки эта схема имеет? Предложить альтернативную структуру данных для каждого края список, который решает эти проблемы. Имеет ли ваша альтернатива недостатки по сравнению с хеш-таблицей?

Итак, если я заменю каждый связанный список на хеш-таблицу, возникают следующие вопросы:

  • каково ожидаемое время, чтобы определить, находится ли ребро на графике?
  • Каковы недостатки?
  • Предложите альтернативную структуру данных для каждого списка ребер, который решает эти проблемы.
  • У вашей альтернативы есть недостатки по сравнению с хэш-таблицей?

У меня есть следующие частичные ответы:

  • Я думаю, что ожидаемое время - O (1), потому что я просто перехожу на Hashtable t = Adj [u], затем возвращаю t.get(v);
  • Я считаю, что недостатком является то, что Hashtable займет больше места, чем связанный список.

По другим двум вопросам я не могу понять.

Кто-нибудь может дать мне ключ?

Ответы

Ответ 1

Это зависит от хэш-таблицы и того, как она обрабатывает конфликты, например, предположим, что в нашей хэш-таблице каждая запись указывает на список элементов, имеющих один и тот же ключ.

Если распределение элементов достаточно равномерно, средняя стоимость поиска зависит только от среднего количества элементов в каждом списке (коэффициент загрузки). поэтому среднее число элементов в каждом списке равно n/m, где m - размер нашей хеш-таблицы.

  • Ожидаемое время, чтобы определить, является ли ребро на графике O (n/m)
  • больше места, чем связанный список, и больше времени запроса, чем матрица смежности. Если наша хеш-таблица поддерживает динамическое изменение размера, нам потребуется дополнительное время для перемещения элементов между старыми и новыми хеш-таблицами, и если бы нам не понадобилось пространство O (n) для каждой хэш-таблицы, чтобы иметь время запроса O (1), которое приводит к пространству O (n ^ 2). также мы только что проверили ожидаемое время запроса, а в худшем случае время запроса может быть похоже на связанный список (O (степень (u))), поэтому лучше использовать матрицу смежности, чтобы иметь детерминированное время запроса O (1) и O (n ^ 2).
  • прочитайте выше
  • да, например, если мы знаем, что каждая вершина нашего графа имеет не более d смежных вершин, а d меньше n, то для использования хэш-таблицы потребуется O (nd) пространство вместо O (n ^ 2) и будет иметь ожидаемое время запроса O (1).

Ответ 2

Ответ на вопрос 3 может быть двоичным деревом поиска.

В матрице смежности каждой вершине следует массив из V элементов. Эта стоимость O (V) -пространства приводит к быстрому (O (1) -time) поиску ребер.

В списке смежности каждая вершина сопровождается списком, который содержит только n смежных вершин. Этот пространственно-эффективный способ приводит к медленному поиску (O (n)).

Хэш-таблица является компромиссом между массивом и списком. Он использует меньше места, чем V, но требует поиска коллизий при поиске.

Двоичное дерево поиска - это еще один компромисс - минимальная стоимость пространства равна таковой из списков, а средняя временная стоимость в поиске - O (lg n).

Ответ 3

Вопросы 3 и 4 очень открыты. Помимо мыслей из двух других, одна проблема с хэш-таблицей заключается в том, что она не является эффективной структурой данных для сканирования элементов от начала до конца. В реальном мире иногда довольно часто перечислять все соседи для данной вершины (например, BFS, DFS) и что-то компрометирует использование прямой хеш-таблицы.

Одним из возможных решений для этого является объединение существующих ковшей в хеш-таблице вместе, чтобы они образовали двусвязный список. Каждый раз, когда добавляется новый элемент, подключайте его к концу списка; Всякий раз, когда элемент удаляется, удалите его из списка и соответствующим образом установите связь. Если вы хотите выполнить общее сканирование, просто просмотрите этот список.

Недостатком этой стратегии, конечно, является больше пространства. Для каждого элемента есть служебная накладка с двумя указателями. Кроме того, добавление/удаление элемента занимает больше времени, чтобы построить/исправить связь.

Я не слишком беспокоюсь о столкновениях. Хэш-таблица вершины хранит своих соседей, каждая из которых уникальна. Если его ключ уникален, вероятность столкновения отсутствует.