Список смежности. Таблица, высота которой равна количеству вершин. В каждой строке перечисляются вершины, в которые из данной есть ребро.
| исходная вершина | конечные вершины |
| 1 | 2 |
| 2 | 1, 3, 4 |
| 3 | 4 |
| 4 | 3 |
Для приведенного примера список смежности будет выглядеть как показано в таблице.
В следующей таблице приведены сравнительные характеристики количества памяти или времени работы программы при каждом способе представления графа. Здесь N – количество вершин, M – количество ребер графа.
| Матрица смежности | Список ребер | Списки смежности | |
| Требуемая память | O(N2) | O(M) | O(M) |
| Поиск ребра | O(1) | O(M) | O(M) |
| Перебор всех ребер | O(N2) | O(M) | O(M) |
| Добавление/удаление ребра | O(1) | O(1) | O(1) |
Примечания для преподавателей
Данная тема практически не привязана ни к каким другим и может даваться в начале курса (не считая обхода в глубину, который иногда реализуют рекурсивно). В частности, она представляет возможность для шлифовки умений работать в двухмерными массивами, файлами и циклами и может использоваться для этих целей.
В частности, существует достаточно большой набор «технических» задач, которые могут являться элементами более сложных программ, а с другой стороны служить закреплению материала по данной теме. Примеры таких несложных задач приведены ниже.
Задача A. Проверка на неориентированность
По заданной квадратной матрице n*n из нулей и единиц определите, может ли данная матрица быть матрицей смежности простого неориентированного графа.
Формат входных данных
Входной файл содержит число n (1 < n < 100) - размер матрицы, и затем n строк по n чисел, каждое из которых равно 0 или 1 — саму матрицу.
Формат выходных данных
Выведите в выходной файл «YES» если приведенная матрица может быть матрицей смежности простого неориентированного графа и «NO» в противном случае.
Пример
input.txt output.txt
| 3 0 1 1 1 0 1 1 1 0 | YES |
| 3 0 1 0 1 0 1 1 1 0 | NO |
| 3 0 1 0 1 1 1 0 1 0 | NO |
Задача B. Петли
По заданной матрице смежности неориентированного графа определите, содержит ли он петли. Формат входных данных
Входной файл содержит число n (1 < n < 100) — количество вершин графа и затем n строк по n чисел, каждое из которых равно 0 или 1 — его матрицу смежности.
Формат выходных данных
Выведите в выходной файл «YES» если граф содержит петли и «NO» в противном случае.
Пример
input.txt output.txt
| 3 0 1 1 1 0 1 1 1 0 | NO |
| 3 0 1 0 1 1 1 0 1 0 | YES |