Реализация графа с помощью AdjacencyLists - PullRequest
Новая
       73

Реализация графа с помощью AdjacencyLists

0 голосов
/ 24 мая 2018

Я хочу реализовать (в Java) класс Graph, используя AdjacencyLists, я бы использовал этот класс на минимальном остовном дереве для Prim's алгоритма.

Я читал, что есть много способов сделать это, но я не могу использовать структуры данных, основанные на более простых примитивных типах данных (LinkedList, стек и т. Д.), Поэтому я подумал, что, возможно, хорошим решением будет использованиеHashTable и объединить их с ArrayList вместо LinkedList.

Я прочитал, что целью объединения LinkedList с HashTable является объединение преимуществ LinkedList (оптимальное перечисление списка смежностивершина) и HashTable (быстрый поиск и добавление ребер).

Я задаюсь вопросом о двух вещах:

  • Могу ли я сохранить эти свойства, используя ArrayList вместо LinkedList?

  • Было бы лучше использовать HashTableсвязан с другим HashTable?

    Есть еще какие-нибудь предложения?Если я использую HashTable, что будет лучшим способом решения коллизий?Я думал о раздельной цепочке.

1 Ответ

0 голосов
/ 24 мая 2018

Я предполагаю, что желаемой структурой графа будет HashTable<Vertex,ArrayList<Pair<Vertex,Float>>>, сопоставляющая каждую вершину с ее смежными вместе с весом ребра.

Вы можете использовать ArrayList, так как вам не нужно удалять обработанные ребра из списка смежности.

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

Обратите внимание, что, хотя подход HashMap + ArrayList является эффективным с точки зрения пространства и достаточен для запуска этого алгоритма в O (V ^ 2) это не рекомендуется для плотных графов, когда требуется много поисков ребер.Проверка того, существует ли ребро от A до B, является линейной по количеству смежных вершин A или B. Если вы хотите получить их в O (1), вам нужен второй HashTable для хранения ребер.Пример приведен в JGraphT Library .

Также обратите внимание, что обычно рекомендуется использовать HashMap вместо HashTable

...