На этом шаге мы рассмотрим представление графов с помощью структуры Вирта.
Используем для представления графа в памяти ЭВМ подход Никлауса Вирта [1, с.211-219], который предполагает построение динамической структуры со многими связями. Вершины графа представляются линейным списком, состоящим из заголовочных узлов. Каждый заголовочный узел содержит четыре поля.
Если указатель P указывает на заголовочный узел, представляющий вершину Q графа, то:
- поле (*P).Key содержит информацию, связанную с вершиной Q;
- поле (*P).Count содержит количество вершин, "предшествующих" данной;
- поле (*P).Next содержит указатель на заголовочный узел, представляющий следующую вершину графа (если такая вершина есть) в списке заголовочных узлов;
- каждый заголовочный узел является заглавным звеном списка узлов второго типа, называемых дуговыми узлами. Такой список мы будем называть списком смежности. Поле (*P).Trail указывает на список смежности, представляющий дуги, выходящие из вершины Q графа (английское слово "Trail" переводится как "тащиться, свисать, волочиться").
Каждый узел списка смежности содержит два поля: Id и Next, причем если Q указывает на дуговой узел, представляющий дугу (A,B), то:
- поле (*Q).Id указывает на заголовочный узел, представляющий вершину B графа;
- поле (*Q).Next указывает на дуговой узел, представляющий следующую дугу, выходящую из вершины A графа (если такая дуга есть).
Каждый дуговой узел содержится в единственном списке смежности, представляющем все дуги, выходящие из данной вершины графа.
Вывод. Каждый заголовочный узел содержит поля Key, Count и два указателя:
- первый указывает на список смежных дуг, выходящих из вершины графа,
- второй - на следующий заголовочный узел в списке заголовочных узлов.
Каждый дуговой узел содержит два указателя:
- на следующий дуговой узел в списке смежности и
- на заголовочный узел, представляющий ту вершину графа, которая является концом дуги.
На рисунке показан ориентированный граф и его представление с помощью структуры Вирта (символ N обозначает NULL):
Рис.1. Представление графа с помощью структуры Вирта
(1)Вирт H. Алгоритмы + структуры данных = программы. - М.: Мир, 1985. - 406 с.
На следующем шаге мы рассмотрим реализацию простейших операций над графом, представленным структурой Вирта.
