Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Списки смежности
|
|
Определение 9.7. Пусть G=(V, E) - ориентированный граф, v - вершина из V. Список смежности Lv для вершины v включает все смежные с ней вершины, т.е.
Представление графа G=(V, E) c n вершинам и V= { v1,..., vn} с помощью списков смежности состоит из списков смежности всех вершин: Lv1, Lv2,..., Lvn.
Размер этого представления сравним с суммой числа вершин и ребер графа. Оно позволяет легко переходить по ребрам от вершины к ее соседям. В программах списки смежности представляются списковыми структурами, которые легко реализуются во всех языках программирования.
Пример 9.1. Рассмотрим следующий граф G=(V, E):
Он показан на рис. 9.2.
Построим для него определенные выше представления.
1. Матрица смежности.
2. Матрица инцидентности.
3. Списки смежности.
Графы: представления, достижимость и связность