Главная » Java, Структуры данных и алгоритмы » Прохождение графов

0

Пр9хождение (обход) — это системная процедура исследования графа посредством обращения ко всем его узлам и путям. Эффективным обход считается в том случае, когда обращение к узлам и путям выполняется за пропорциональное их количеству время, то есть в линейном времени. Рассмотрим два типа прохождения ненаправленного графа под названиями «поиск в глубину» (depth-first search) и «поиск в ширину» (breadth-first search), а также возможность расширения этих методик для прохождения направленных графов.

Поиск в глубину

Первым рассмотрим алгоритм обхода под названием поиск в глубину (depth-first search — DFS) в ненаправленном графе. Этот алгоритм используется для ряда вычислений в графе, включая поиск пути из одного узла в другой, определение связности графа, и создания остовного дерева связного графа.

Поиск в глубину в ненаправленном графе С аналогичен прохождению лабиринта с использованием нити и баллончика с краской, чтобы не заблудиться. Начинаем от некоторого узла s графа С, инициируем который, привязав один конец нити к узлу s и отметив его краской как уже виденный. Узел $ теперь является текущим — назовем его и. Затем движемся по G вдоль (произвольного) пути (w,v), инцидентного для текущего узла и. Если путь (u,v) ведет к уже пройденному (то есть отмеченному краской) узлу v, немедленно возвращаемся в и. Если, напротив, (u,v) ведет в новый узел, отматываем нить и двигаемся в v. Здесь также производится отметка краской v как пройденного узла, и он становится текущим. После чего вся процедура повторяется. При этом возможно попадание в тупик, то есть из текущего узла и все проходящие через него пути будут вести в уже пройденные узлы. Таким образом, выбор любого из путей, проходящих через w, приводит обратно в и. Чтобы разрешить эту ситуацию, сматываем обратно нить, следуя по ней в обратном направлении по пути, приведшему в и, в предшествовавший ему узел v, который снова становится текущим узлом, и движемся по любому другому из проходящих через v и не использованных путей. Если все сквозные пути v приводят в уже пройденные узлы, то нить снова сматывается, и возвращаемся в предшествовавший v узел, после чего повторяем все занЪвр. Таким образом продолжаем двигаться в обратном направлении, пока не обнаружим узел, не все пути которого пройдены, выбираем один из них и следуем дальше. Процесс заканчивается, если в результате движения назад возвращаемся в точку отправления, не обнаружив ни одного непройденного сквозного для узла s пути. Этот простой процесс обходит все пути графа G в элегантной и систематизированной манере (см. рис. 12.6).

Можно представить обход типа поиска в глубину, для которого пути ориентируются в направлении их прохождения при обходе, различая от- крывающие пути, по которым входили в новые узлы — discovery edges, или tree edges, и обратные пути, которые вели в уже пройденные узлы — back etfges (см. рис. 12.6, f).

Далее покажем, что «обратные пути» формируют остовное дерево связного компонента узла отправления s. Пути, не входящие в это дерево, называют «обратными», поскольку считаем, что дерево растет из корневого узла отправления, а эти пути ведут обратно к одному из своих предшественников, находящихся в этом дереве.

Псевдокод алгоритма поиска в глубину, в котором используется рекурсия для реализации аналога нити и механизм определения свойств

узла (аналог отметки краской при его прохождении), приводится во фрагменте кода 12.1.

Алгоритм DFS((7,v):

Input: граф G и узел v в G.

Output: маркировка узлов в качестве пройденных и обратные пути.

for all путей е в G.incidentEdges(v) do if путь е не пройден then w <- G.opposite(\/,e) if узел w не пройден then

отмаркировать е как открывающий путь рекурсивно вызвать DFS(G,w) else

отмаркировать е как обратный путь Фрагмент кода 12.1. Алгоритм DFS

Есть ряд свойств алгоритма поиска в глубину, многие из которых вытекают из механизма, с помощью которого алгоритм различает две группы путей ненаправленного графа — открывающие и обратные. Например, поскольку обратные пути всегда связывают узел v с ранее пройденным узлом w, каждый обратный путь предполагает наличие цикла в G, состоящего из прямых путей от и до v плюс обратный путь (u,v).

Утверждение 12.5 указывает еще на несколько важных свойств метода поиска в глубину.

Утверждение 12.5. Пусть G — ненаправленный граф, где выполняется обход путем поиска в глубину, узлом отправления которого служит s. Тогда:

•   при прохождении обходятся все узлы связного компонента узла я;

•   прямые пути формируют остовное дерево связного компонента узла я.

Доказательство. Обоснование того, что проходятся все узлы в связном компоненте узла s, основано на доказательстве от противного. Предположим, что имеется хотя бы один узел v в связном компоненте узла s, который не был пройден, a w пусть будет первым непройденным узлом в маршруте прохождения от s до v (естественно, может быть и так, что v = w). Поскольку w — это первый непройденный узел этого обхода, у него должен быть соседний узел и, который был пройден. Но если узел и уже пройден, то и путь (u,w) должен был быть опробован. Следовательно, утверждение, что w не был пройден, неверно, что означает отсутствие в связном компоненте узла s непройденных узлов.

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

Л*с. 72.6. Пример поиска в глубину в графе с точкой отправления в узле А. Пути к непройденным узлам обозначены непрерывной линией, а к пройденным узлам — пунктиром: (а) исходный граф; (Ь) маршрут прохождения новых узлов, прослеживаемый из А до пути в уже открытый узел {В,А) — самый успешный вариант; (с) остановка в F, оказавшемся тупиком; (d) после возвращения в С, продолжение движения по пути (C,G) и вхождение в другой тупик /; (е) после возвращения в G\ (0 после возвращения в N

С точки зрения времени выполнения поиск в глубину является достаточно эффективным методом обхода графа. Отметим, что DFS вызывается в каждом узле только один раз, а каждый путь проходится ровно дважды — по разу для каждой из его конечных точек. Таким образом, если ns узлов и ms путей находятся в связном компоненте узла s, алгоритм DFS, начинающий свой обход из узла s, выполняется за О(ns +m5) времени при следующих условиях:

•      граф представлен структурой данных со следующими значениями времени выполнения:

?     метод incidentEdges(v) выполняется за 0(degree(v)) времени;

?     методы hasNext() и nextEdge() из Edgelterator, возвращаемые методом incidentEdges(v), выполняются за 0(1) времени;

?     метод opposite(v,?) выполняется за 0(1) времени;

?     структура списка смежности отвечает этим требованиям, а структура матрицы смежности — не отвечает.

•      имеется способ маркировки пройденных узлов или путей и проверки, пройдены они или нет, за 0(1) времени. Один из способов — расширение функциональности позиций (приводится ниже). Другим способом является использование вспомогательной хеш-та- блицы для хранения пройденных узлов и путей. Эта схема отвечает требованиям вероятностного подхода, поскольку хеш-таблица поддерживает операции маркировки (ввода) и проверки (поиска) за 0(1) предполагаемого времени (см. раздел 8.3).

Модель «декоратор»

Маркировка пройденных узлов при поиске в глубину (DFS) является примером проектной модели под названием декоратор. Эта модель применяется для добавления атрибутов, или «декорирования» имеющихся объектов. Каждый атрибут идентифицируется особым элементом — декоратором а, который представляет собой нечто вроде ключа, отличающего данный атрибут. Интуитивно атрибут а является именем элемента декоратора, и далее у этого атрибута имеется возможность принимать разные значения для различных объектов, помечаемых такими атрибутами. Использование декораторов мотивировано требованием некоторых алгоритмов и структур данных добавлять вспомогательные переменные или временно перемещать данные в объекты, в которых таких переменных обычно нет. Следовательно, декоратор представляет собой пару (атрибут, значение), которую можно динамически присоединять к объекту. Например, узлы в AVL-дереве или красно-черном дереве могут быть дополнены атрибутами высоты или цвета. В примере с поиском в глубину можно было бы добавить в узлы и пути атрибуты прохождения и логические значения.

Реализовать модель декоратора для всёх позиционных контейнеров можно с помощью добавления в АТД «позиция» следующих методов:

has(fl): проверяет наличие в позиции атрибута а\ ‘ get(fl): возвращает значение атрибута а\ set(fl,x): устанавливает для х значение атрибута а\ destroy(fl): удаляет атрибут а и ассоциированное с ним значение.

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

Утверждение 12.6. Пусть G — граф из п узлов и т путей, представленный структурой списка смежности. DFS-обход графа G может быть выполнен за 0(п + т) времени. К тому же существует алгоритм на основе DFS со временем выполнения 0(п + т), предназначенный для решения следующих задач: л

•   проверка, является ли G связным;

•   построение остовного дерева в G, если он связный;

•   вычисление связных компонентов графа <7;

•      вычисление маршрута между двумя заданными узлами G или сообщение об отсутствии такого маршрута;

•   вычисление цикла в G или сообщение об отсутствии циклов.

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

Реализация DFS на Java

Во фрагментах кода 12.2—12.4 приводится Java-реализация стандартного обхода поиском в глубину с помощью класса DFS, который может быть применен для работы в конкретном приложении с помощью переопределения метода execute, активизирующего вычисления, и следующих методов, вызываемых в разное время рекурсивным шаблонным методом dfsTraversal:

•      isDone(): вызывается для определения необходимости досрочного завершения обхода;

•      finishVisit(Vertex v): вызывается, если все инцидентные пути узла v уже пройдены;

•    result(): для вызова результата работы dfsTraversal.

Использование модели проектирования шаблонных методов для DFS

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

Механизм, используемый для идентификации уже пройденных в процессе обхода узлов и Путей, инкапсулируется в вызовы методов isVisited, visit и unVisit. Приводимая реализация (см. фрагмент кода 12.4) предполагает, что позиции узлов и путей поддерживают модель декоратора. Или, с другой стороны, можно установить словарь позиций для хранения пройденных узлов и путей.

Расширим класс DFS и переопределим некоторые из вспомогательных методов во фрагменте кода 12.3 для выполнения нетривиальных дей- • ствий. Такой подход отвечает модели проектирования стандартных методов, поскольку о ни. определяют поведение шаблонного метода dfsTraversal.

Фрагменты кода 12.5—12.7 иллюстрируют различные способы применения метода dfsTraversal в классах, расширяющих DFS. Например, класс ConnectivityTesterDFS (фрагмент кода 12.5) проверяет, является ли граф связным. Он подсчитывает узлы, доступные для DFS-обхода, начинающегося в одном йз них, и сравнивает это количество с общим количеством узлов графа.

Г[25] Стандартный обход поиском в глубину в графе с помощью модели

*                      проектирования методов. Подкласс должен переопределять методы,

*             чтобы расширить свойства обхода. 7 public abstract class DFS {

Г Граф, в котором выполняется обход. 7 protected InspectableGraph G; /** результат обхода 7 protected Object visitResult;

Г* Выполняет поиск в глубину.

*       @param g Input graph.

*       @param начало узла Start для обхода -

*’@param info вспомогательная информация (используется * подклассами).

public Object execute(lnspectableGraph g, Vertex start, Object info) { G = g;

for (Positionlterator pos = G.positions(); pos.hasNext(); )

unVisit(pos.nextPosition()); return null;

} /**

/** Рекурсивный шаблонный метод стандартного DFS-обхода * @ param v узел Start для обхода

7

protected Object dfsTraversal (Vertex v) { initResult(); start Visit(v); visit(v);

for (Edgetterator inEdges = G.incidentEdges(v); inEdges.hasNext(); ) { Edge nextEdge = inEdges.nextEdge();_

if (lisVisited(nextEdge)) { // обнаружен непройденный путь, пройти visit(nextEdge);

Vertex w = G.opposite(v, nextEdge);

if (lisVisited(w)) { // w не пройден, это непройденный путь traverseDiscovery(nextEdge, v); if (!isDone())

visitResult = dfsTraversal(w);

}

else // w пройден, это обратный путь traverseBack(nextEdge, v);

}

}

finishVisit(v); return result();

}

Фрагмент кода 12.2. Переменные экземпляров и шаблонный метод dfsTraversal класса DFS, выполняющего DFS-обход в графе (продолжение во фрагменте кода 12.3)

/** Вспомогательный метод, специализации DFS. */ protected void initResult() {} // инициирует результат (вызывается первым) protected void startVisit(Vertex v) {} // вызывается при первом обращении к v protected void finishVisit(Vertex v) {} // вызывается при выходе из v protected void traverseDiscovery(Edge e, Vertex from) {} // прямой путь protected void traverseBack(Edge e, Vertex from) {} // обратный путь protected boolean isDone() { return false; } // DFS закончен раньше? protected Object result() { return new ObjectQ; } // результат работы DFS

Фрагмент кода 12.3. Вспомогательные методы для специализации метода dfsTraversal класса DFS (фрагмент кода 12.2)

/** Атрибут и его два значения для статуса позиции. 7 protected static Object STATUS = new Object(); // атрибут статуса protected static Object VISITED = new Object(); // значение пройденного protected static Object UNVISITED = new Object(); // значение

// непройденного

/** Отмаркировать позицию как пройденную. 7

protected void visit(Position р) { p.set(STATUS, VISITED); }

/** Отмаркировать позицию как непройденную. 7

protected void unVisit(Position р) { p.set(STATUS, UNVISITED); }

/** Проверить, пройдена ли позиция. 7

protected boolean isVisited(Position р) {

return (p.get(STATUS) == VISITED); }

Фрагмент кода 12.4. Методы visit, unVisit и isVisit класса DFS (фрагмент кода 12.2), реализованные с помощью маркируемых позиций

/** Этот класс специализирует DFS определения связности графа. 7 public class Connectivity TesterDFS extends DFS { protected int reached;

public Object execute(lnspectableGraph g, Vertex start, Object info) { super.execute(g, start, info); reached = 0; if (!G.isEmptyO) {

Vertex v = G.aVertex(); dfsTraversal(v);

}

return (new Boolean(reached == G.numVertices()));

}

public void startVisit(Vertex v) { reached++; } }

Фрагмент кода 12.5. Специализация класса DFS для проверки связности графа

Класс FindPathDFS (фрагмент кода 12.6) отыскивает маршрут между парой узлов — точкой отправления и точкой назначения. Он начинает поиск в глубину из первого узла — точки отправления. Далее движемся по открывающим путям из этой точки до текущего узла. Если узел оказывается непройденным, добавляем его в конец маршрута, а по окончании обработки удаляем из маршрута. Обход заканчивается после нахождения узла назначения, и маршрут возвращается в виде итератора узлов. Заметим, что маршрут, обнаруженный данным классом, состоит только из открывающих путей.

/** Данный класс специализирует DFS для вычисления маршрута между

*       двумя            *

*       определенными узлами. */

public class FindPathDFS extends DFS { protected Sequence path; protected boolean done; protected Vertex target;

/**@ param info узел назначения данного пути

return итератор узлов в маршруте от точки отправления

*       до точки назначения или пустой итератор, если такого маршрута

*       в графе не существует. */

public Object execute(lnspectableGraph g, Vertex start, Object info) { super.execute(g, start, info); path = new NodeSequence(); done = false;

target4= (Vertex) info; // конечный узел хранится в параметре info dfsTraversal(start);

return new VertexlteratorAdapter(path.elements());

}

protected void startVisit(Vertex v) { path.insertLast(v); if (v == target) done = true;

}

protected void finishVisit(Vertex v) { if (Idone)

path.remove(path.last());

}

protected boolean isDone() { return done;

}

}

Фрагмент кода 12.6. Специализация класса DFS для определения маршрута между двумя узлами. Вспомогательный класс VertexIteratorAdapter предоставляет адаптер из последовательности в итератор узла

Класс FindCycleDFS (фрагмент кода 12.7) находит цикл в связном компоненте указанного узла v с помощью обхода поиском в глубину из этого узла, заканчивающегося при обнаружении обратного пути. Возвращает (иногда пустой) итератор цикла, содержащий обнаруженный обратный путь.

Л* Специализация DFS, для поиска петли в связном компоненте

* узла отправления, public class FindCycleDFS extends DFS {

protected Sequence cycle; // последовательность узлов в цикле protected boolean done; protected Vertex cycleStart, target;

/** @return итератор путей петли в компоненте узла отправления. 7 public Object execute(lnspectableGraph g, Vertex start, Object info) { super.execute(g, start, info); cycle = new NodeSequence(); done = false; dfsTraversal(start);

if (!cycle.isEmpty() && start != cycleStart) {

Position Iterator pos = cycle.positions();                                                     1

while (pos.hasNext()) { // удаляет пути из start в cycleStart Position p = pos.nextPosition(); Edge e = (Edge) p.element(); cycle, remove(p);

if (g.arelncident(cycleStart, e)) break;

}

}

return new EdgelteratorAdapter(cycle.elements());

}

protected void finishVisit(Vertex v)

if ((!cycle.isEmpty()) && (Idone)) cycle.remove(cycle.last());

}

protected void traverseDiscovery(Edge e, Vertex from) { if (Idone) cycle.insertLast(e);

}

protected void traverseBack(Edge e, Vertex from) { if (Idone) {

cycle.insertLast(e); // обратный путь e завершает создание цикла cycleStart = G.opposite(from, e); done = true;

}

}

protected boolean isDone() { return done; }

}

Фрагмент кода 12.7. Специализация класса DFS для поиска петли в связном компоненте указанного узла. Вспомогательный класс EdgelteratorAdapter представляет адаптер из последовательности в итератор путей

Источник: Гудрич М.Т. Г93 Структуры данных и алгоритмы в Java / М.Т. Гудрич, Р. Тамассия; Пер. с англ. A.M. Чернухо. — Мн.: Новое знание, 2003. — 671 е.: ил.

По теме:

  • Комментарии