Лекция 4. Поиск остовного дерева в ширину и поиск в глубину. Алгоритмы Прима и Краскала (жадный) для поиска
Дана неориентированная сеть N, нужно выбрать подмножество дуг, образующих дерево Т, в котором существует путь между каждой парой узлов сети. Дерево такого типа называется остовным деревом сети.
Во многих приложениях нужно в определенном порядке посетить все узлы графа, т. е. построить остовное дерево.
Рассмотрим следующие два общих способа обхода, называемые поиском в ширину (BFS, breadth-first-search) и поиском в глубину (DFS, depth-first-search).
Поиск в ширину, BFS. Выбираем произвольно узел графа G, назовем этот узел V0и затем посетим всех соседей V0в произвольном порядке, например, это узлы V1 , V2, …, Vi. После посещения всех соседей V0 начать обход заново из V1 (первого посещенного соседа узла V0) и посетить все соседние с V1 узлы, скажем, V11, V12,…, V1j, потом все новые узлы, соседние с V2, скажем, V21, V22, …, V2k. Систематически получаем:
Порядок
Соседние узлы
V0
V1 , V2, …, Vi
V1
V11, V12,…, V1j
V2
V21, V22,…, V2j
…
…
V11
V11 1, V11 2,…, V11 j
V12
V12 1, V12 2,…, V12 j
На рис. 11 можно взять за V0 узел Va, тогда узлы можно посетить в следующем порядке:
V0, Vb, Vc, Vd, Ve, Vf,
V0, V1, V2, V11, V21 , V111.
Рис. 11.
Если взять в качестве V0 узел Vb, то можно посетить вершины в порядке
Vb , Va , Vc, Vd, Ve, Vf,
V0, V1 , V2, V3, V21, V31.
Замечание 1. После посещения нового узла можно посетить соседей нового узла в произвольном порядке. Здесь используется соглашение о том, что при необходимости выбора узлы посещаются в алфавитном порядке.
Замечание 2. Если пометить дугу, соединяющую посещенный узел с ранее посещенным узлом, то все эти помеченные дуги образуют остовное дерево графа G; если же каждая дуга имеет длину 1, то остовное дерево является деревом кратчайших путей из V0во все остальные узлы G.
Поиск в глубину, DFS. Выбираем произвольно вершину V0, а затем следуем по ребру е01 в узел Vi , потом следуем по ребру e12 в узел V2, соседний с V1 . Вобщем случае, после посещения узла Vi следуем по ребру eijв узел Vj, если Vj ранее еще не был посещен. Далее применяем рекурсивно этот процесс к Vj и выбираем ребро ejkв узел Vk. Если вершина Vj уже была посещена, то возвращаемся в Viи выбираем другое ребро. Если все ребра, инцидентные Vi, уже выбраны и нельзя найти ни одной новой вершины, то возвращаемся из Vj в предыдущую вершину, за которой идет Vi, и проверяем ей инцидентные ребра.
Если на рис. 11 начать с вершины Vb, то можно посетить узлы в следующем порядке (упорядочение определяется не единственным образом):
Vb, Vc, Va, Vd, Ve, Vf.
Дуги, следующие в новые вершины, образуют остовное дерево. Это дуги: ebc, eca, ecd, ede, eef.
Можно сравнить два способа посещения узлов. При BFS нужно проверить все ребра, инцидентные узлу, перед переходом к новому узлу. Таким образом, операция последовательно выполняется веером из узлов. При DFS переход к новому узлу осуществляется только после того, как найден новый узел, и происходит проникновение в глубину графа. Только тогда, когда все ребра ведут в старые вершины, идет возврат к предыдущему узлу и из него опять возобновляется DFS.
Алгоритмы BFS и DFS имеют одинаковую сложность для самого неблагоприятого случая. Сложность алгоритма для самого неблагоприятного случая – это приблизительная мера максимального числа действий, требуемых, чтобы выполнить алгоритм. Это функция размера входных данных, которые непосредственно в нашем случае были представлены графом (например, О(n)). Так как алгоритмы имеют одинаковую сложность, то ни один из них не имеет преимуществ перед другим. Тем не менее, для целого ряда специфических графов один алгоритм мог бы производить дерево покрытия эффективнее, чем другой. Например, поиск «по глубине» эффективнее для графа «колеса», а поиск «ширине» для графа «Мальтийский крест».