Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Void tsR(int v)
|
|
{
pre[v] = cnt++;
for (int w = 0; w < D.V(); w++) if (D.edge(w, v))
if (pre[w] == -1) tsR(w); post[v] = tcnt; postI [tcnt++] = v; }
Часть 5. Алгоритмы на графах
|
РИСУНОК 19.25. ТОПОЛОГИЧЕСКАЯ СОРТИРОВКА ГРАФА DAG МЕТОДОМ УДАЛЕНИЯ ИСТОКОВ
Вершина О, будучи истоком (на нее не указывает ни одно ребро), может оказаться первой при топологической сортировке этого графа (слева вверху). Если удалить 0 (а также все ребра, которые ведут из этой вершины в другую вершину), то истоками в получающемся при этом графе DAG становятся вершины 1 и 2 (слева, вторая диаграмма сверху), которые можно сортировать при помощи того же алгоритма. Этот рисунок служит иллюстрацией работы программы 19.8, которая производит выбор истоков (заштрихованные вершины в каждой диаграмме), используя для этой цели дисциплину обслуживания FIFO, хотя на каждом шаге может быть выбран любой из источников. Посмотрите также на рис. 19.26, на котором представлено содержимое структур данных, способное повлиять на выбор, который выполняет рассматриваемый алгоритм. В результате топологической сортировки, показанной на этом рисунке, получается следующий порядок узлов: 0 82173 6549111012.
Глава 19. Орграфы и ориентированные ациклические графы
|
| Эффективная реализация этого алгоритма есть классический пример алгоритма топологической сортировки (см. раздел ссылок). Во-первых, возможно, существование некоторого множества истоков, и в силу этого обстоятельства для их отслеживания мы должны поддерживать очередь (для этого подойдет любая обобщенная очередь). Во-вторых, мы должны выявить в заданном графе DAG истоки, которые остаются после удаления того или иного истока. Мы можем решить эту задачу, поддерживая вектор, проиндексированный именами вершин, который отслеживает по- |
лустепень захода каждой вершины. Вершины с полустепенью захода 0 суть истоки, поэтому мы можем инициализировать очередь с одним просмотром графа DAG (используя поиск в глубину или какой-либо другой метод, обеспечивающий просмотр всех ребер). Затем, пока очередь истоков не опустеет, мы выполняем следующие операции:
■ Удаляем исток из очереди и присваиваем
ему соответствующую метку.
■ Уменьшаем на единицу значения элемен
тов вектора полустепеней захода, соответ
ствующих вершинами назначения каждого
из ребер удаленной вершины.
■ Если в результате уменьшения значения
какой-либо элемент принимает значение О,
вставляем соответствующую вершину в
очередь истоков.
Программа 19.8 содержит реализацию этого метода, в которой применяется очередь FIFO, a рис. 19.26 служит иллюстрацией ее работы на примере рассматриваемого нами DAG, при этом динамика примера, представленного на рис. 19.25, обрастает дополнительными подробностями.
Очередь истоков не опустеет до тех пор, пока не будет помечена каждая вершина графа DAG, поскольку подграф, индуцированный еще не помеченными вершинами, всегда есть DAG, и каждый DAG имеет, по меньшей мере, один исток. В самом деле, мы можем использовать алгоритм для проверки, является ли заданный граф графом DAG, предполагая, что должен существовать цикл в подграфе, индуцированном еще непомеченными вершинами, если очередь опустеет до того как все вершины будут помечены (см. упражнение 19.104).
РИСУНОК 19.26. ТАБЛИЦА ПОЛУСТЕПЕНЕЙ ЗАХОДА И СОДЕРЖИМОЕ ОЧЕРЕДИ
Данная последовательность описывает содержимое таблицы полустепеней захода (слева) и очередь истоков (справа) во время выполнения программы 19.8 на примере DAG, соответствующего рис. 19.25. В любой заданный момент времени очередь истоков содержит узлы с полустепенью захода, равной 0. Производя считывания сверху вниз мы удаляем из очереди истоков крайний левый узел, уменьшаем на единицу значения полустепени захода элементов, соответствующих каждому ребру, исходящему из этого узла, и добавляем в очередь истоков все вершины, элементы таблицы которых принимают значения 0. Например, вторая строка таблицы отражает результат удаления вершины 0 из очереди истоков, с последующим (поскольку DAG содержит ребра 0- 1, 0-2, 0-3, 0-5 и 0-6) уменьшением на единицу значений элементов, соответствующих вершинам 1, 2, 3, 5 и 6, и добавлением вершин 2 и 1 в очередь истоков (поскольку значения их полустепеней захода уменьшилось до 0). Считывание крайних слева элементов в очереди истоков сверху вниз дает топологическое упорядочение рассматриваемого графа.
Часть 5. Алгоритмы на графах
Программа 19.8. Топологическая сортировка, основанная на очереди истоков______________
Этот класс реализует тот же интерфейс, что ипрограммы 19.7 и 19.8. Он поддерживает очередь истоков и использует таблицу, которая отслеживает полустепени захода каждой вершины графа DAG, индуцированного вершинами, которые еще не удалены из очереди.
Когда мы удаляем исток из очереди, мы уменьшаем значения полустепеней захода, соответствующих каждой вершине в его списке смежных вершин (и помещаем в очередь каждую вершину, соответствующую элементу таблицы, принимающему значение 0). Вершины покидают очередь в порядке топологической сортировки.
# include " QUEUE.cc"
template < class Dag> class dagTS
{ const Dag & D;
vector< int> in, ts, tsI; public:
dagTS (const Dag & D): D(D),
in(D.V(), 0), ts(D.V(), -1), tsI(D.V(), -1) { QUEUE< int> Q;
for (int v = 0; v < D.V(); v++) {
typename Dag:: adjIterator A(D, v);
for (int t = A.beg();! A.end(); t = A.nxt())
in[t]++; } for (int v = 0; v < D.V(); v++)
if (in[v] == 0) Q.put(v); for (int j = 0;! Q.empty(); j++) {
ts[j] = Q.get(); tsl[ts[j]] = j;
typename Dag:: adjIterator A(D, ts[j]);
for (int t = A.beg();! A.end(); t = A.nxt())
if (--in[t] == 0) Q.put(t); } }
int operator[](int v) const { return ts[v]; } int relabel(int v) const { return tsl[v]; } };
Обработка вершин в порядке, образованном топологической сортировкой, представляет собой базовую технологию обработки графов DAG. Классическим примером может служить задача определения длины самого длинного пути в графе DAG. Рассматривая вершины в порядке, обратном устанавливаемому топологической сортировкой, легко вычислить самый длинный путь, начинающийся в каждой вершине v. Для этого потребуется добавить единицу к максимальной из длин путей, начинающихся в каждой из вершин, достижимых из v через одно ребро. Благодаря топологической сортировке все такие длины известны во время обработки вершины v, так что никакие другие пути из v после этого выявляться не будут. Например, выполняя сканирование слева направо обратной топологической сортировки, показанной на рис. 19.23, мы можем достаточно быстро вычислить следующую таблицу длин максимальных путей, возникающих в каждой вершине демонстрационного графа, который показан на рис. 19.21.
5 12 11 10 946321078 0010234450656
Глава 19. Орграфы и ориентированные ациклические графы
Например, 6, соответствующая 0 (третий столбец справа), показывает, что существует путь длиной 6, начинающийся в 0, о чем мы знаем, поскольку существует ребро 0-2; ранее мы определили, что длина самого длинного пути из вершины 2 равна 5 и что ни одно из ребер, исходящих из 0, не ведет в узел, имеющий более длинный путь.
Всякий раз, когда мы используем топологическую сортировку для подобного рода приложений, перед нами встает проблема выбора одного из следующих способов разработки реализации:
■ Использование класса DAGts в АТД DAG с последующей обработкой вершин в
очередности, задаваемой вектором, который он вычисляет.
■ Обработка вершин после рекурсивных вызовов в рамках DFS.
■ Обработка вершин по мере того, как они выбираются из очереди в процессе то
пологической сортировки на базе очереди истоков.
В литературе показано, что все эти методы используются в реализациях, выполняющих обработку DAG, в этой связи следует подчеркнуть, что все они эквивалентны. Мы рассмотрим другие приложения топологической сортировки в упражнениях 19.111 и 19.114 и в разделах 19.7 и 21.4.