Список смежности
-
Основы списка смежности
- Список смежности — это представление графа, где каждая вершина связана с набором соседей.
- Используется в компьютерных программах для представления графов.
-
Реализация списка смежности
- Гвидо ван Россум предложил использовать хэш-таблицу для представления вершин и связанных с ними соседей.
- Кормен и др. предложили использовать индексные номера для представления вершин и односвязные списки для соседей.
- Гудрич и Тамассия предложили объектно-ориентированную структуру с классами вершин и ребер.
-
Операции со списком смежности
- Основная операция — это представление списка соседей вершины за постоянное время.
- Проверка наличия ребра между двумя вершинами может быть выполнена за время, пропорциональное минимальной степени вершин.
-
Сравнение с матрицей смежности
- Матрица смежности более экономична в пространстве для разреженных графов, но требует больше времени для операций.
- Список смежности занимает больше места для плотных графов, но обеспечивает более эффективное представление.
-
Структуры данных и операции
- Матрица смежности компактна и удобна для ориентирования, но требует больше места для разреженных графов.
- Список смежности прост в использовании и эффективен для операций, связанных с соседями.
-
Рекомендации и ссылки
- Библиотека Boost Graph предлагает эффективную реализацию списка смежности.
- В статье есть внешние ссылки для дальнейшего чтения.
Полный текст статьи: