Иерархический список
Собственно, этот способ представления графов является всего лишь внутренней реализацией списка смежности: в одном линейном списке содержатся номера "начальных вершин", а в остальных - номера смежных вершин или указатели на эти вершины. В качестве примера (см. рис. 11.11) приведем иерархический список, задающий орграф, изображенный на рис. 11.6.
Рис. 11.11. Пример иерархического списка
type uk_versh = ^vershina; uk_duga = ^duga vershina = record number : integer; sled_vershina : uk_versh; spisok_dug : uk_duga end; duga = record konec_dugi : uk_versh; sled_duga : uk_duga; end;
Очевидное преимущество такого способа представления графов заключается в экономичном использовании памяти. И даже небольшая избыточность данных, к которой приходится прибегать в случае неориентированного графа, задавая каждое ребро как две дуги, искупается гибкостью всей структуры, что особенно удобно при необходимости частых перестроений в процессе работы программы.
Если в приведенные описания типов данных добавить поля, которые могли бы хранить веса вершин и дуг, то таким же способом можно задавать и взвешенные графы (орграфы).
