Неориентированный граф: оптимальное создание

#графы #java #алгоритм

Здравствуйте! Всем добрый день! Подскажите, пожалуйста, каким образом оптимальнее
создавать неориентированный граф, столько разных структур существует в Java:


Можно в виде матрицы смежности, создав просто 2-мерный массив (что не очень оптимально,
так что сразу был отброшен)
Можно переделать тип Iterator в Bag, сделав список смежных вершин
(тогда это будет выглядеть примерно так: http://algs4.cs.princeton.edu/13stacks/Bag.java.html,
неплохой вариант, в принципе)
Можно сделать все это с помощью Map и TreeMap (видел один пример, понравился по компактности,
но не знаю, будет ли это приемлемо, или же нет)
Также вот увидел вариант с помощью Hashmap


Вот в общем, такие у меня варианты есть. Я не силен в Java, еще только начинаю в
нем разбираться. Подскажите, каким образом решить данный вопрос. Спасибо большое заранее!
    

Ответы

Ответ 1

Конкретный язык прграммирования тут ни при чем! Видимо, если Вы не сильны в Java,
то пока не сильны и вообще в алгоритмах и структурах данных. Поэтому рекомендую не
думать на данном этапе о сверхэффективности Вашего кода.
Используйте классические структуры данных для представления графа: матрицу смежности
или списки смежности (это 1й и 2й пункты из Вашего вопроса). Возьмите хорошую книгу
и реализуйте граф так, как там описано внутри класса граф (в зоне private).
Добавьте public-интерфейс, который нужен для конкретной задачи.
Реализуйте по книге алгоритмы обхода графа. Запрогрпмируйте какую-нибудь олимпиадную
задачу с помощью Вашего класса. Если Вы сделаете обе реализации, сможете сравнить производительность.
Успехов!