Список смежности графа.

По отношению к памяти списки смежности менее требовательны, чем матрицы смежности, для их хранения нужно O(|V|+|E|) памяти. Такой список графически можно изобразить в виде таблицы, столбцов в которой – два, а строк не больше чем вершин в графе. В качестве примера возьмем смешанный граф:adjacency list


В нем 6 вершин (|V|) и 5 ребер (|E|). Из последних 2 ребра направленные и 3 ненаправленные, и, причем из каждой вершины выходит, как минимум одно ребро в другую вершину, из чего следует, что в списке смежности этого графа будет |V| строк.

Вершина выхода

Вершины входа

1

5

2

6

3

2, 5

4

5

5

1, 4

6

2

В i строке и 1 столбце указана вершина выхода, а в i строке и 2 столбце – вершина входа. Так, к примеру, из вершины 5 выходят два ребра, входящие в вершины 1 и 4.

Теперь перейдем непосредственно к программной реализации списка смежности. Количество вершин и ребер будут задаваться с клавиатуры, поэтому установим ограничения, иначе говоря, определим две константы, одна из которых отвечает за максимально возможное число вершин (Vmax), другая – ребер (Emax).

Далее, нам понадобятся три одномерных целочисленных массива:

  • terminal[1..Emax] – хранит вершины, в которые входят ребра;
  • next [1..Emax] – содержит указатели на элементы массива terminal;
  • head[1..Vmax] – содержит указатели на начала подсписков, т. е. на такие вершины записанные в массив terminal, с которых начинается процесс перечисления всех вершин смежных одной i-ой вершине.

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

Код программы на C++:

Код программы на Pascal:

Работа двух приведенных программ идентична, а отличаются они друг от друга, лишь символикой, используемой в ЯП, поэтому дальнейшие рассуждения будут касаться их обеих. Итак, первое действие, на которое стоит обратить внимание это запрос на ввод суммы вершин (n) и ребер (m) графа (пользователь должен заранее знать эти данные).

Далее, запускается цикл ввода ребер (смежных вершин). Условие в этом цикле нужно для того, чтобы узнать, какое введено ребро. Если введено направленное ребро, то функция add вызывается 1 раз, иначе – 2, тем самым внося сведения, что есть ребро как из вершины v в вершину u, так и из u в v. После того как список смежности сформирован, программа выводит его на экран.

Для этого использован цикл от 1 до n, где n – количество вершин, а также вложенный в него цикл, который прекращает свою работу тогда, когда указатель на следующий элемент для i-ой вершины отсутствует, т. е. все смежные ей вершины уже выведены.

Функция add производит добавление ребер в изначально пустой список смежности:

Add(v, u)
k:=k+1
terminal[k]:=u
next[k]:=head[v]
head[v]:=k

Чтобы сделать это, производятся операции с формальными параметрами, вспомогательной переменной k и тремя одномерными целочисленными массивами. Значение переменной k увеличивается на 1. Затем в k-ый элемент массива terminal записывается конечная для некоторого ребра вершина (u). В третий строке k-ому элементу массива next присваивается адрес следующего элемента массива terminal. Ну и в конце массив head заполняется указателями на стартовые элементы, те с которых начинается подсписок (строка в таблице) смежных вершин с некоторой i-ой вершиной.

Так как в ячейке на пересечении i-ой строки и 2-ого столбца могут быть записаны несколько элементов (что соответствует нескольким смежным вершинам) назовем каждую строку в списке смежности его подсписком. Таким образом, в выведенном списке смежности, элементы подсписков будут отсортированы в обратном порядке. Но, как правило, порядок вывода смежных вершин (в подсписках) попросту неважен.


Похожие записи:

Оставить комментарий

Ваш e-mail не будет опубликован. Обязательные поля отмечены *