Поиск по графу в глубину. Топологическая сортировка

 

Один из способов исследования всех вершин и ребер графа основан на процедуре прохождения графа методом поиска с возвращением, т.е. на исследовании графа в глубину. Рассмотрим это на примере неориентированного графа. Когда мы посещаем вершину v Î V, мы идем по одному из ребер (v, w), инцидентному v. Если вершина w уже пройдена (посещалась ранее), мы возвращаемся в v и выбираем другое ребро. Если вершина w еще не пройдена, то заходим в нее и применяем процесс рекурсивно к w. Если все ребра, инцидентные вершине v, уже просмотрены, мы идем назад к ребру (u, v), по которому пришли в v, и продолжаем исследование ребер, инцидентных u. Процесс заканчивается, когда все вершины пройдены и когда мы пытаемся вернуться назад из вершины, с которой началось исследование.

a: b, c, e

b: a, c, d

c: a, b, d, e

d: b, c

e: a, c

 

Рис. 3.3. Граф G.   Структура смежности G.    Пройденный граф

 

Как видно на рис. 3.3 поиск в глубину превращает исходный неориентированный граф G в ориентированный граф , индуцируя на каждом ребре направление прохождения. Сплошные линии ® образуют ориентированное остовное дерево.

Ориентированное остовное дерево, получаемое в результате поиска в глубину на простом связанном неориентированном графе, называется DFS -деревом. Ребра  называются обратными, т.к. ведут от потомка к предку.

Для реализации процедуры поиска в глубину нам необходимо отличать уже пройденные вершины от еще не пройденных. Этого можно достигнуть путем постепенной нумерации вершин числами по мере того, как мы в них попадаем.

 

 

Топологическая сортировка

 

Простейшим случаем использования техники поиска в глубину на ориентированных графах является способ пометки вершины ациклического ориентированного графа G = (V, E) числами 1, 2, …, | V |  так, что если из вершины i в вершину j идет ориентированное ребро, то i < j; такой способ пометки называется топологической сортировкой вершин графа G. Например, вершины графа на рис. 3.4 (б) топологически отсортированы, а на
рис. 3.4 (а) нет.

а)                                                      б)

                                         

Рис. 3.4. Ациклические ориентированные графы

 

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

Топологическая сортировка начинается с отыскания вершины графа G = (V, E), из которой не выходят ребра, и присвоения этой вершине наибольшего номера, а именно | V |. Эта вершина удаляется из графа вместе с входящими в нее ребрами. Поскольку оставшийся ориентированный граф также ациклический, мы повторяем процесс и присваиваем следующий наибольший номер | V | – 1 вершине, из которой не выходят ребра и т. д.