Как стать автором
Обновить

Комментарии 25

Написано сумбурно, но обзор добротный — ссылок много и даже не все они фиолетовые. Спасибо.
старался структурировать в том порядке как эти структуры обычно перечисляются в классическах учебниках по алгоритмам. Также пытался обратить внимание только на самое важное, полная картина — в исходниках и жавадоках.
Графовые структуры и алгоритмы нужно в библиотеках реализовывать. Зачем их тащить в JDK?
Наверное, было бы неплохо добавить всё это отдельным пакетом.
конечно, по аналогии того же java.util.zip
графовые алгоритмы то давно устоявшиеся и изведаны +это добавило бы еще универсальности платформе
Тогда какой критерий затаскивания в jdk? Почему например gzip включили?
По моему графы даже уже в энторпрайзе можно встретить
Граф — не структура данных, а достаточно высокоуровневая модель с множеством вариаций, которые редко даже совпадают в прикладных задачах, которая реализуется поверх структур (из JDK или библиотек).
большинство графовых задач решается с испольованием простой модели на смежных списках (adj lists), вот она к примеру: Digraph.java +алгоритм кратчайшего пути — вроде не сильно высокий уровень, вот чего то подобного в jdk не хватает для универсальности.
В чистом виде это нужно только для олимпиадных задач. В практических задачах у вершин и/или ребер есть какие-то метаданные, поэтому они превращаются в объекты. Дополнительные ограничения, эвристики возникают. И т. д.
На практике добавляем generic (Т) value для ноды и ребра +компаратор, все — эвристикам вроде больше ничего не нужно. Графовые алгоритмы — довольно просты, вкратце: сравнение и подсчет весов ребер, перебор исходящих и т.д.
Как идентифицировать ребра? Если только началом и концом, то возникают проблемы с кратными ребрами.
Как идентифицировать вершины? Добавление и удаление вершин будет сбивать их нумерацию.
Вес ребра хранится в value или во внутренних структурах графа? Он целочисленный или действительный? Как обрабатывать погрешности при работе с действительными числами (вдруг у вас есть цикл веса -1e-100, нужно ли выдавать ошибку при поиске кратчайшего пути?)? Разрешены ли отрицательные веса? С отрицательными весами нужно применять другие алгоритмы.
Как передавать вершины между функциями? Как граф + число, граф + объект вершины или объект вершины? В последних случаях, что делать если кто-то сохранит вершину, которую в последствии удалят из графа?
Как удалять ребро за O(1), а не за O(степень вершины)?
Как проверить, есть ли ребро между вершинами за O(1) или может хотя бы за O(log N)?

Как только вы начнете отвечать на подобные вопросы, очень быстро окажется, что нужны десятки различных классов графов. После чего, нужно реализовать дополнительно десятки алгоритмов конвертации между любыми из них.
вы совершенно правы в сложности формализации графовых моделей, но, повторюсь, существует мнение что в 90% графовых задач нет паралельных ребер, нет отрицательных весов и других сложностей, а нужно всего лишь делать какой нибудь topological sort или кратчайший путь.
Автор лукавит, говоря, что отсутствует hash таблица с открытой адресацией — вы забыли о ThreadLocalMap — хранилище для ThreadLocal. Другое дело, что как-то использовать его кроме ThreadLocal нельзя.
спасибо, добавил про нее.
IdentityHashMap, кстати, тоже с открытой адресацией.
вот про это совсем упустил, добавил, спасибо!
Queue — интерфейс (api) LIFO очереди, добавление в начало, удаление с конца за O(1)

Я не java-ист (хотя в данном случае это роли не играет), но стало интересно почему это называется Queue? Queue это разве не FIFO?
Вы правы, это опечатка в статье.

П. С. Пожалуйста, не насилуйте так больше русский язык. «Я не пишу на Яве (Java)»
опечатка, поправил
да, вот выше в камментах тоже указывали на этот топик, только шаблоны проектирования и структуры данных — это все же разные вещи, конечно смежные темы, но граница между ними думаю довольна ясна.
о что то я не заметил — да темы разные но я тут провел параллель с примерами из JDK ))
НЛО прилетело и опубликовало эту надпись здесь
Упустил, но и смысла мало:

LinkedHashMap<K,V> extends HashMap<K,V>

— это ж не новая структура а тот же HashMap с дополнительными ссылками.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий

Публикации

Истории