Графы. Хранение хранить список смежностей как хеш-таблицу. Чем не идеал?

[Kn793]

По-моему это идеальный вариант. Такой способ позволяет как за О(1) узнать смежны ли вершины, так и получить список всех смежных вершин. То-есть объединяет возможности матрицы и списка смежностей.
Но в Кормене вопрос поставлен с явным намёком на минусы...

[Utkin]

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

[Kn793]

Так ведь это и есть список смежностей

[Utkin]

Не совсем. Я писал в противовес в этому http://ru.wikipedia.org/wiki/%D0%9C%...81%D1%82%D0%B8
И кстати, никаких проблем с определением смежности вершин...
Да и еще вопрос, а какие минусы там были:

Но в Кормене вопрос поставлен с явным намёком на минусы...

[Kn793]

И кстати, никаких проблем с определением смежности вершин...

Никаких проблем это значит для определения вы пробегались по всему списку и искали нужную вершину?

Да и еще вопрос, а какие минусы там были:

Это упражнение. Заключается в нахождении этих минусов .

[Utkin]

Зачем ее искать? Они уже все найдены .

[still_alive]

Сообщение от Kn793

По-моему это идеальный вариант. Такой способ позволяет как за О(1) узнать смежны ли вершины, так и получить список всех смежных вершин. То-есть объединяет возможности матрицы и списка смежностей.
Но в Кормене вопрос поставлен с явным намёком на минусы...

На первый взгляд:
1) требуется больше памяти, нежели при списках;
2) элементы в списке смежности нельзя хранить отсортированными по какому-либо критерию;
3) доступ к элементам выполняется медленнее по сравнению с матрицей смежности (варьируется от O(1) до O(N) в зависимости от реализации хеш-таблиц и коэффициентов их заполнения).

[pu4koff]

Сообщение от Kn793

По-моему это идеальный вариант.

Идеальный для чего?

Сообщение от Kn793

Такой способ позволяет как за О(1) узнать смежны ли вершины, так и получить список всех смежных вершин.

О(1) - это идеальный случай при отсутствии коллизий. Вопрос в реализации хеш-функции, размере таблицы, её заполнении,...

Сообщение от Kn793

То-есть объединяет возможности матрицы и списка смежностей.

т.е. наследует и плюсы и минусы. Для каких-то задач будет лучше массивов и списков, для каких-то будет серьезно проигрывать. Вопрос в правильном использовании.

Сообщение от Kn793

Но в Кормене вопрос поставлен с явным намёком на минусы...

Кто есть Кормен?
Итог: способ не идеальный. Может быть лучше для определенных задач, но не для всех и не всегда. Всё зависит от целей и доступных возможностей.