Алгоритмы на графах. Представление графов. Кратчайшие пути из одной вершины, страница 3

Для выполнения поиска в глубину удобно использовать стек (stack). Мы помещаем вершину в стек, когда впервые ее посещаем (т.е. когда начинается обход вершины), и снимаем ее со стека, когда она становится тупиком (т.е. обход вершины завершается). Тупик – это вершина, у которой нет непосещенных смежных вершин. По достижении тупика алгоритм возвращается на одно ребро назад и пытается продолжить посещения смежных непосещенных вершин с этого места. Если поиск в ширину можно назвать обходом для осторожных, то поиск в глубину – это обход для смелых.

Обходы графов. Поиск в глубину

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

Остовные деревья графа

Остовным деревом для связанного неориентированного графа G с n вершинами называется неориентированное дерево, содержащее все n вершин и (n-1) ребер графа. Остовное дерево связывает все вершины графа и из каждой вершины графа можно попасть в любую другую. В полном графе с n вершинами имеется n↑(n-2) остовных деревьев. Для одного и того же графа можно построить несколько остовных деревьев. Пусть G – связанный граф и T – остовное дерево для него.

Остовные деревья графа

• Тогда:
• для любых двух вершин путь между ними единствен;
• если к остовному дереву добавить ребро из оставшихся, не включенных в дерево ребер графа, то возникает ровно один цикл и T перестает быть деревом.
• Под остовным деревом ориентированного графа понимаем такое дерево, в котором одна из вершин графа связана со всеми остальными.

Минимальные остовные деревья

Стоимость (вес) остовного дерева определяется как сумма стоимостей (весов) его ребер. Цель – найти для графа G остовное дерево наименьшей стоимости (минимального веса). Решение задачи прямым поиском имело бы сложность О(nⁿ). Наиболее простым алгоритмом поиска остовного дерева минимального веса является алгоритм Прима, удивительно похожий на алгоритм Дейкстры поиска кратчайшего пути.

Упорядочение графа (топологическая сортировка)

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

Упорядочение графа (топологическая сортировка)

Пример 2. В учебных программах одни предметы опираются на материал других. Топологическая сортировка означает чтение курсов в таком порядке, чтобы ни один курс не читался раньше того курса, на котором он основан. Пример 3. Сетевые методы планирования и управления предполагают, что любая работа может быть выполнена только после того, как будут выполнены опорные работы.

Упорядочение графа (топологическая сортировка)

Пусть имеется ориентированный граф G=(V,E) с произвольно занумерованными вершинами vi, i=1,2,…,n. Граф является упорядоченным, если в отношении каждой его дуги (vi, vj) справедливо неравенство vi<vj. Для этого необходимо выполнить перенумерацию вершин в соответствии с их рангами. Будем считать, что единственная вершина vi, не имеющая входов, имеет нулевой ранг. Для любой другой вершины vj ее ранг равен максимальной длине пути (максимальному числу дуг) от вершины нулевого ранга vi до вершины vj.

Упорядочение графа (топологическая сортировка)

Топологическая сортировка (topological sort) ориентированного ациклического графа G представляет собой такое линейное упорядочение всех его вершин, что если граф G содержит ребро (vi, vj), то vi при таком упорядочении располагается до vj. Топологическую сортировку графа можно рассматривать как такое упорядочение его вершин вдоль горизонтальной линии, что все ребра направлены слева направо. Таким образом топологическая сортировка существенно отличается от обычных видов сортировок.

Упорядочение графа (топологическая сортировка)

Алгоритм упорядочения графа состоит из двух этапов. На первом этапе определяются ранги вершин, на втором этапе осуществляется перенумерация их в соответствии с рангами. Единственной вершине vi, не имеющей входов, присваивается номер 0, причем нумерация вершин одного ранга безразлична. Упорядоченный граф имеет вершины vi с номерами 0, 1, 2, … , n-1.