EssayAI
Блог
Блог
Математика и алгоритмы

Список смежности: представление графа с примерами

8 ноября 2026Время чтения: 8 минут
#теория графов#список смежности#представление графа#алгоритмы#структуры данных
Список смежности: представление графа с примерами

Список смежности - способ представить граф, перечислив для каждой вершины её непосредственных соседей. Например, если от вершины А идут рёбра к Б и В, рядом с А записывают Б и В. Такая запись показывает связи локально: чтобы узнать соседей, достаточно открыть одну строку, а не рассматривать весь рисунок. Ниже построим списки по рёбрам, восстановим по ним граф и сравним их с матрицей смежности. В интерактиве можно добавлять рёбра и наблюдать, как меняются списки и степени вершин.

Что хранит список смежности

Граф G=(V,E)G=(V,E) состоит из множества вершин VV и множества рёбер EE. Две вершины неориентированного графа называют смежными, если между ними есть ребро. Для каждой вершины создаём отдельный список её соседей. Важно, что здесь сосед - вершина на расстоянии ровно одного ребра, а не любая вершина, до которой можно добраться по пути.

Представление часто реализуют как массив или словарь, где ключ - вершина, а значение - коллекция соседей. Слово «список» описывает идею представления: конкретная коллекция может быть динамическим массивом, связным списком или множеством. Выбор влияет на скорость отдельных операций и на расход памяти.

В неориентированном графе ребро А–Б связывает обе вершины равноправно: Б появляется в списке А, а А - в списке Б. На видео выделенное ребро сопоставлено сразу с двумя соответствующими записями; затем выделение переходит к следующему ребру.

Выделенное ребро графа последовательно сопоставляется с двумя записями в списках его концов; у изолированной вершины Д список пуст.

Как построить списки по рёбрам

Возьмём пять вершин А, Б, В, Г, Д и четыре ребра: А–Б, А–В, Б–В, В–Г. Вершина Д не входит ни в одно ребро, но остаётся частью графа. Это важно: по одним лишь рёбрам нельзя узнать, сколько в графе изолированных вершин, поэтому множество вершин задают отдельно.

Начнём с пяти пустых списков. Для каждого ребра добавим его концы в списки друг друга. Так, А–Б даёт Б в строке А и А в строке Б; затем А–В даёт В в строке А и А в строке В. Повторив действие для оставшихся рёбер, получим:

ВершинаСоседиСтепень
АБ, В2
БА, В2
ВА, Б, Г3
ГВ1
Д∅0

Порядок соседей не определяет граф: например, строка В: Г, Б, А описывает те же рёбра. Однако порядок может повлиять на то, какую вершину алгоритм обхода посетит первой. Если задача требует конкретного порядка, его нужно оговорить отдельно, например перебирать соседей по алфавиту.

Пять вершин и их списки смежности: четыре ребра дают восемь записей, список изолированной вершины пуст
Пять вершин и их списки смежности: четыре ребра дают восемь записей, список изолированной вершины пуст

Для простого неориентированного графа без петель длина списка вершины равна её степени. В примере сумма степеней равна 2+2+3+1+0=82+2+3+1+0=8, то есть удвоенному числу рёбер: 2∣E∣=2⋅4=82|E|=2\cdot4=8. Каждое ребро даёт по одной записи на каждом конце. Это удобная проверка подсчёта, хотя одна правильная сумма ещё не доказывает, что все строки составлены верно.

Как восстановить граф по спискам

Сначала нарисуйте все вершины, включая вершины с пустыми списками. Затем для каждой записи соедините соответствующую пару. В нашем примере строка А даёт рёбра А–Б и А–В, строка Б добавляет Б–В, а строка В - В–Г. Запись А в строке Б не создаёт второе ребро А–Б: она подтверждает уже нарисованное ребро.

Для простого неориентированного графа проверьте симметрию: если Б есть в списке А, то А должна быть в списке Б. Если обратной записи нет, условие либо содержит ошибку, либо описывает ориентированный граф. При параллельных рёбрах повторения имеют смысл: число вхождений Б в список А должно совпадать с числом вхождений А в список Б.

Петля соединяет вершину с самой собой. Соглашения о записи петли различаются: например, в реализации Princeton Algorithms её записывают дважды, чтобы длина списка совпадала со степенью, в которую петля вносит два. Прежде чем считать степени по спискам с петлями, уточните принятое правило.

Ориентированный и взвешенный граф

У дуги есть начало и конец. Обычно в список вершины записывают исходящих соседей: дуга А→Б добавляет Б в список А, но сама по себе не добавляет А в список Б. Обратная запись появляется только при наличии отдельной дуги Б→А.

Например, для дуг А→Б, Б→А и Б→В списки исходящих соседей таковы: А: Б; Б: А, В; В: ∅. Их длины равны полустепеням исхода: 1, 2 и 0. Сумма длин равна числу дуг, то есть трём, а не шести. Если нужно быстро находить входящие дуги, можно дополнительно хранить отдельные списки входящих соседей.

Взвешенное ребро хранит дополнительное значение: стоимость, длину или время. Вместо одного имени соседа в строку помещают пару «сосед, вес». Для неориентированного ребра А–Б веса 7 в обеих строках появятся пары Б, 7 и А, 7. Во взвешенном ориентированном графе запись добавляется только в список начала дуги. Например, для алгоритма Дейкстры нужны и соседи, и веса исходящих рёбер; его стандартная версия требует неотрицательных весов.

Ещё один способ проверить ориентированный пример - выписать дуги по строкам. Из А выходит одна дуга А→Б; из Б выходят Б→А и Б→В; из В не выходит ни одной. Таким образом, обратные дуги между А и Б являются двумя разными связями. Пустой список В не запрещает входящую дугу Б→В: он сообщает только об отсутствии исходящих дуг. В списках входящих соседей, напротив, у В была бы запись Б. Если в условии говорится просто «список смежности ориентированного графа», полезно явно указать выбранное соглашение до вычислений.

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

Матрица смежности для nn вершин - таблица n×nn\times n: ячейка показывает наличие ребра между соответствующими вершинами. В простом неориентированном графе она симметрична относительно главной диагонали. Список хранит отдельные строки переменной длины и не выделяет ячейку под каждую отсутствующую связь.

Операция или ресурсОбычный список смежностиМатрица смежности
ПамятьO(n+m)O(n+m)O(n2)O(n^2)
Перебор соседей вершины vvO(deg⁡(v))O(\deg(v))O(n)O(n)
Проверка ребра vv–uuдо O(deg⁡(v))O(\deg(v))O(1)O(1)

Здесь mm - число рёбер, а проверка в списке предполагает последовательный поиск. Хеш-множество или отсортированный список меняют оценки операций и имеют собственные издержки. Если вершин много, а рёбер сравнительно мало, списки особенно удобны для хранения и обхода соседей. Для плотного графа или частых проверок конкретной пары матрица может оказаться удобнее. Это сравнение относится к обычным реализациям; подробнее устройство и оценки приведены в учебнике Open Data Structures.

Зачем списки нужны алгоритмам

При обходе графа в ширину алгоритм извлекает вершину из очереди и просматривает её соседей, чтобы обнаружить ещё не посещённые вершины. Списки позволяют не проверять все возможные пары: при полном обходе каждая вершина и каждая запись соседства рассматриваются ограниченное число раз. Поэтому общая оценка - O(n+m)O(n+m), если учитывать и инициализацию данных для всех вершин.

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

Частые ошибки

  • Записали ребро только с одной стороны. Для неориентированного графа без петель добавьте каждую пару в обе строки; для дуги правило другое.
  • Потеряли изолированную вершину. Пустая строка нужна: она отличает вершину без соседей от отсутствующей вершины.
  • Соединили вершины, связанные только путём. В список попадают непосредственные соседи, а не все достижимые вершины.
  • Посчитали каждую запись отдельным ребром. В обычном неориентированном графе без петель каждая связь встречается дважды; повторные записи могут также обозначать параллельные рёбра.
  • Смешали входящие и исходящие дуги. Для ориентированного графа явно укажите, какой тип соседей хранит список.

FAQ

Обязательно ли сортировать соседей?

Нет. Сортировка полезна для воспроизводимого порядка обхода и некоторых способов поиска, но на сам набор рёбер она не влияет. Нужно лишь соблюдать оговорённое представление повторных рёбер.

Можно ли получить матрицу из списков?

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

Почему пустой список не означает отсутствие вершины?

Пустой список говорит, что у данной вершины нет записанных соседей. Сама вершина присутствует как ключ или индекс в структуре, поэтому её можно учитывать при подсчёте числа вершин и компонент связности.

Коротко

Список смежности сопоставляет каждой вершине её непосредственных соседей. Для простого неориентированного графа каждое ребро даёт две записи, а изолированная вершина сохраняется с пустым списком. В ориентированном графе обычно перечисляют исходящие дуги; веса хранят рядом с соседями. Представление занимает O(n+m)O(n+m) памяти и удобно для алгоритмов, которым нужно перебирать соседей.

Доверьте текст нейросети EssayAI

Открыть EssayAI

Бесплатно, на русском языке и без VPN

Читайте также

Дерево Фенвика: суммы и обновления по шагам

Дерево Фенвика: суммы и обновления по шагам

Дерево Фенвика хранит суммы блоков массива и помогает быстро отвечать на запросы и менять элементы. Разбираем lowbit, пример вычислений, реализацию на Python и сложность операций.

8 ноября 20269 минут
Стек на списке: реализация push и pop через массив

Стек на списке: реализация push и pop через массив

Как реализовать стек на списке: индекс вершины, амортизированная сложность push O(1), расширение массива вдвое при переполнении и почему pop не освобождает память сразу.

11 июня 20267 минут
Высота и глубина дерева: формулы и примеры

Высота и глубина дерева: формулы и примеры

Разбираем высоту и глубину дерева в информатике: точные определения, формулы для полного двоичного и вырожденного дерева, примеры задач и типичные ошибки.

11 июня 20268 минут
Дерево двоичного поиска: построение и операции

Дерево двоичного поиска: построение и операции

Дерево двоичного поиска: как устроены узлы, как построить BST по ключам, выполнить обход и удалить элемент, от чего зависит высота и сложность операций.

8 ноября 20268 минут
Доминирующее множество в графе: определение и примеры

Доминирующее множество в графе: определение и примеры

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

8 ноября 20268 минут
Обходы двоичного дерева: порядки и примеры

Обходы двоичного дерева: порядки и примеры

Обходы двоичного дерева на одном примере: прямой, симметричный, обратный и по уровням. Как работают рекурсия, стек и очередь, какие результаты и сложность.

8 ноября 20268 минут