Главная » Статьи для тега "смежности"

Структура матрицы смежности

Добавлено Дата: 5 January, 2012 категория: Java, Структуры данных и алгоритмы

Как и в случае со списком смежности, матрица смежности расширяет структуру списка путей с помощью дополнительных компонентов. В данном случае в список путей добавляется матрица (двухмерный массив) А, что позволяет определять смежности пар узлов за пропорциональный 0(1) промежуток времени. Как будет показано далее, такое повышение скорости требует значительных объемов памяти.

Читать »

Структура списка смежности

Добавлено Дата: 13 December, 2011 категория: Java, Структуры данных и алгоритмы

для. графа G расширяет структуру списка путей, добавляя сведения, которые поддерживают прямой доступ к инцидентным путям (и, таким образом, к объединенным узлам) каждого узла. В то время как список путей рассматривает отношение уЗла и инцидентного пути со стороны последнего, структура списка смежности позволяет рассмотреть это отношение с обеих сторон. Такой симметричный подход позволяет реализовывйть методы работы с узлами АТД «граф» с помощью списка смежности гораздо быстрее, хотя обе структуры списка смежности используют пространство, пропорциональное количеству узлов и путей в графе. включает в себя все структурные компоненты списка путей и дополнительно включает следующее:

Читать »

Структуры данных для графов

Добавлено Дата: 9 December, 2011 категория: Java, Структуры данных и алгоритмы

Существует несколько способов реализации АТД «граф» с помощью конкретных структур данных. Рассмотрим три наиболее известных: список путей (edge list structure), список смежности (adjacency list structure) и матрицу смежности (adjacency matrix). В каждой из них используется контейнер (список или вектор) для хранения узлов графа. Хранение же путей между первыми двумя и последней структурами значительно различается. Структура списка путей и структура списка смежности хранят только пути, непосредственно имеющиеся в графе, в то время как матрица смежности сохраняет заглушки для каждой пары узлов (независимо от того, соединены они путем или нет). Это различие предполагает, что для графа G из п узлов и т путей список путей или список смежностй будут занимать 0(п + т) места, а матрица требует 0(п2) места.

Читать »