WikiSort.ru - Программирование

ПОИСК ПО САЙТУ | о проекте
Этот цикличный ненаправленный граф может быть описан тремя списками {b, c}, {a, c}, {a, b}.

Список смежности — один из способов представления графа в виде коллекции списков вершин. Каждой вершине графа соответствует список, состоящий из "соседей" этой вершины.

Особенности реализации

Граф на картинке наверху имеет следующий список смежности:
a смежно к b, c
b смежно к a, c
c смежно к a, b

Есть несколько вариаций представление графа списком смежности, отличающихся особенностями ассоциации вершин и коллекций соседей, реализацией коллекций, включаются ли рёбра и вершины в коллекции соседей или только вершины, способами представления рёбер и вершин.

  • Реализация, предложенная Гвидо ван Россумом, использует хеш-таблицу для ассоциации каждой вершины со списком смежных вершин. Нет явного представления рёбер в этой структуре[1][2][3][4].
  • Кормен и другие предложили реализацию, в которой вершины представлены числовым индексом в массиве, в котором каждая ячейка массива ссылается на однонаправленный связанный список соседних вершин.[5]
  • Объектно-ориентированный список смежности, предложенный Гудричем и Таммасией, содержит специальные классы вершин и рёбер. Каждый объект вершины содержит ссылку на коллекцию рёбер. Каждый объект ребра содержит ссылки на исходящую и входящую вершины.[6]

Сравнение с матрицей смежности

Основной источник: [7]
Сравнение с матрицей смежности
Операция Список смежности Матрица смежности
Проверка на наличие ребра (x,y)
Определение степени вершины
Использование памяти для разреженных графов
Вставка/удаление грани[источник не указан 944 дня]
Обход графа

Ссылки

  1. Гвидо ван Россум. Python Patterns — Implementing Graphs (1998).
  2. Multimap at guava.
  3. Контейнер Multimap в языке c++ на основе бинарного дерева.
  4. Контейнер Multimap в языке c++ на хеш-таблицы.
  5. Introduction to Algorithms, Second Edition. — MIT Press and McGraw-Hill, 2001. — P. 527–529 of section 22.1: Representations of graphs. ISBN 0-262-03293-7.
  6. Michael T. Goodrich and Roberto Tamassia. Algorithm Design: Foundations, Analysis, and Internet Examples. — John Wiley & Sons, 2002. ISBN 0-471-38365-1.
  7. Steven Skiena. Тhe Algorithm Design Manual (2nd ed.). — 2010. — P. 152 of section 5.2: Data Structures for Graphs. ISBN 0-387-00163-8.

Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".

Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.

Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .




Текст в блоке "Читать" взят с сайта "Википедия" и доступен по лицензии Creative Commons Attribution-ShareAlike; в отдельных случаях могут действовать дополнительные условия.

Другой контент может иметь иную лицензию. Перед использованием материалов сайта WikiSort.ru внимательно изучите правила лицензирования конкретных элементов наполнения сайта.

2019-2024
WikiSort.ru - проект по пересортировке и дополнению контента Википедии