Как найти ширину графа

Текущая версия страницы пока не проверялась опытными участниками и может значительно отличаться от версии, проверенной 26 апреля 2021 года; проверки требуют 6 правок.

У этого термина существуют и другие значения, см. BFS.

Поиск в ширину (англ. breadth-first search, BFS) — один из методов обхода графа. Пусть задан граф и выделена исходная вершина . Алгоритм поиска в ширину систематически обходит все ребра для «открытия» всех вершин, достижимых из , вычисляя при этом расстояние (минимальное количество рёбер) от до каждой достижимой из вершины. Алгоритм работает как для ориентированных, так и для неориентированных графов.^[1]

Поиск в ширину имеет такое название потому, что в процессе обхода мы идём вширь, то есть перед тем как приступить к поиску вершин на расстоянии , выполняется обход вершин на расстоянии .

Поиск в ширину является одним из неинформированных алгоритмов поиска^[2].

Работа алгоритма[править | править код]

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

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

Неформальное описание[править | править код]

1. Поместить узел, с которого начинается поиск, в изначально пустую очередь.
2. Извлечь из начала очереди узел и пометить его как развёрнутый.
   • Если узел является целевым узлом, то завершить поиск с результатом «успех».
   • В противном случае, в конец очереди добавляются все преемники узла , которые ещё не развёрнуты и не находятся в очереди.
3. Если очередь пуста, то все узлы связного графа были просмотрены, следовательно, целевой узел недостижим из начального; завершить поиск с результатом «неудача».
4. Вернуться к п. 2.

Примечание: деление вершин на развёрнутые и не развёрнутые необходимо для произвольного графа (так как в нём могут быть циклы). Для дерева эта операция не нужна, так как каждая вершина будет выбрана один-единственный раз.

Формальное описание[править | править код]

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

Рекурсивная формулировка:

BFS(start_node, goal_node) {
  return BFS'({start_node}, ∅, goal_node);
}
BFS'(fringe, visited, goal_node) {
  if(fringe == ∅) {
    // Целевой узел не найден
    return false; 
  }
  if (goal_node ∈ fringe) {
    return true;
  }
  return BFS'({child | x ∈ fringe, child ∈ expand(x)}  visited, visited ∪ fringe, goal_node);
}

Итеративная формулировка:

BFS(start_node, goal_node) {
 for(all nodes i) visited[i] = false; // изначально список посещённых узлов пуст
 queue.push(start_node);              // начиная с узла-источника
 while(! queue.empty() ) {            // пока очередь не пуста
  node = queue.pop();                 // извлечь первый элемент в очереди
  if(node == goal_node) {
   return true;                       // проверить, не является ли текущий узел целевым
  }
  visited[node] = true;               // пометить текущую ноду посещенной
  foreach(child in expand(node)) {    // все преемники текущего узла, ...
   if(visited[child] == false) {      // ... которые ещё не были посещены ...
    queue.push(child);                // ... добавить в конец очереди...
    visited[child] = true;            // ... и пометить как посещённые
   }
  }
 }
 return false;                        // Целевой узел недостижим
}

Реализация на Pascal:

function BFS(v : Node) : Boolean;
begin
  enqueue(v);
  while queue is not empty do
  begin
    curr := dequeue();
    if is_goal(curr) then
    begin
      BFS := true;
      exit;
    end;
    mark(curr);
    for next in successors(curr) do
      if not marked(next) then
      begin
        enqueue(next);
      end;
  end;
  BFS := false;
end;

Свойства[править | править код]

Обозначим число вершин и рёбер в графе как и соответственно.

Пространственная сложность[править | править код]

Так как в памяти хранятся все развёрнутые узлы, пространственная сложность алгоритма составляет ^[2].

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

Временная сложность[править | править код]

Так как в худшем случае алгоритм посещает все узлы графа, при хранении графа в виде списков смежности, временная сложность алгоритма составляет ^[2][3].

Полнота[править | править код]

Если у каждого узла имеется конечное число преемников, алгоритм является полным: если решение существует, алгоритм поиска в ширину его находит, независимо от того, является ли граф конечным. Однако если решения не существует, на бесконечном графе поиск не завершается.

Оптимальность[править | править код]

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

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

История и применения[править | править код]

Поиск в ширину был формально предложен Э. Ф. Муром в контексте поиска пути в лабиринте^[4]. Ли независимо открыл тот же алгоритм в контексте разводки проводников на печатных платах^[5][6][7].

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

См. также[править | править код]

• Поиск с ограничением глубины
• Поиск в глубину
• Алгоритм Дейкстры

Примечания[править | править код]

Литература[править | править код]

• T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein. Introduction to Algorithms. — 3rd edition. — The MIT Press, 2009. — ISBN 978-0-262-03384-8.. Перевод 2-го издания: Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн. Алгоритмы: построение и анализ = Introduction to Algorithms. — 2-е изд. — М.: «Вильямс», 2006. — С. 1296. — ISBN 0-07-013151-1.
• Левитин А. В. Глава 5. Метод уменьшения размера задачи: Поиск в ширину // Алгоритмы. Введение в разработку и анализ — М.: Вильямс, 2006. — 576 с. — ISBN 978-5-8459-0987-9

Ссылки[править | править код]

• Steven M. Rubin Computer Aids for VLSI Design. Chapter 4: Synthesis Tools
• Волновой алгоритм поиска пути
• Поиск в ширину на Pascal и C++

Время на прочтение
5 мин

Количество просмотров 155K

Доброго времени суток.

Представляю вашему вниманию перевод статьи «Algorithms on Graphs: Let’s talk Depth-First Search (DFS) and Breadth-First Search (BFS)» автора Try Khov.

Что такое обход графа?

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

Двумя основными алгоритмами обхода графа являются поиск в глубину (Depth-First Search, DFS) и поиск в ширину (Breadth-First Search, BFS).

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

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

DFS следует концепции «погружайся глубже, головой вперед» («go deep, head first»). Идея заключается в том, что мы двигаемся от начальной вершины (точки, места) в определенном направлении (по определенному пути) до тех пор, пока не достигнем конца пути или пункта назначения (искомой вершины). Если мы достигли конца пути, но он не является пунктом назначения, то мы возвращаемся назад (к точке разветвления или расхождения путей) и идем по другому маршруту.

Давайте рассмотрим пример. Предположим, что у нас есть ориентированный граф, который выглядит так:

Мы находимся в точке «s» и нам нужно найти вершину «t». Применяя DFS, мы исследуем один из возможных путей, двигаемся по нему до конца и, если не обнаружили t, возвращаемся и исследуем другой путь. Вот как выглядит процесс:

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

Мы достигли конца p1, но не нашли t, поэтому возвращаемся в s и двигаемся по второму пути.

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

Мы вновь достигли конца пути, но не нашли t, поэтому возвращаемся назад. Следуем по третьему пути и, наконец, достигаем искомой вершины «t».

Так работает DFS. Двигаемся по определенному пути до конца. Если конец пути — это искомая вершина, мы закончили. Если нет, возвращаемся назад и двигаемся по другому пути до тех пор, пока не исследуем все варианты.

Мы следуем этому алгоритму применительно к каждой посещенной вершине.

Необходимость многократного повторения процедуры указывает на необходимость использования рекурсии для реализации алгоритма.

Вот JavaScript-код:

// при условии, что мы имеем дело со смежным списком
// например, таким: adj = {A: [B,C], B:[D,F], ... }
function dfs(adj, v, t) {
	// adj - смежный список
	// v - посещенный узел (вершина)
	// t - пункт назначения

	// это общие случаи
	// либо достигли пункта назначения, либо уже посещали узел
	if(v === t) return true
	if(v.visited) return false

	// помечаем узел как посещенный
	v.visited = true
	// исследуем всех соседей (ближайшие соседние вершины) v
	for(let neighbor of adj[v]) {
		// если сосед не посещался
		if(!neighbor.visited) {
			// двигаемся по пути и проверяем, не достигли ли мы пункта назначения
			let reached = dfs(adj, neighbor, t)
			// возвращаем true, если достигли
			if(reached) return true
		}
	}
	// если от v до t добраться невозможно
	return false
}

Заметка: этот специальный DFS-алгоритм позволяет проверить, возможно ли добраться из одного места в другое. DFS может использоваться в разных целях. От этих целей зависит то, как будет выглядеть сам алгоритм. Тем не менее, общая концепция выглядит именно так.

Анализ DFS

Давайте проанализируем этот алгоритм. Поскольку мы обходим каждого «соседа» каждого узла, игнорируя тех, которых посещали ранее, мы имеем время выполнения, равное O(V + E).

Краткое объяснение того, что означает V+E:

V — общее количество вершин. E — общее количество граней (ребер).

Может показаться, что правильнее использовать V*E, однако давайте подумаем, что означает V*E.

V*E означает, что применительно к каждой вершине, мы должны исследовать все грани графа безотносительно принадлежности этих граней конкретной вершине.

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

Далее, поскольку мы используем рекурсию для обхода каждой вершины, это означает, что используется стек (бесконечная рекурсия приводит к ошибке переполнения стека). Поэтому пространственная сложность составляет O(V).

Теперь рассмотрим BFS.

Поиск в ширину

BFS следует концепции «расширяйся, поднимаясь на высоту птичьего полета» («go wide, bird’s eye-view»). Вместо того, чтобы двигаться по определенному пути до конца, BFS предполагает движение вперед по одному соседу за раз. Это означает следующее:

Вместо следования по пути, BFS подразумевает посещение ближайших к s соседей за одно действие (шаг), затем посещение соседей соседей и так до тех пор, пока не будет обнаружено t.

Чем DFS отличается от BFS? Мне нравится думать, что DFS идет напролом, а BFS не торопится, а изучает все в пределах одного шага.

Далее возникает вопрос: как узнать, каких соседей следует посетить первыми?

Для этого мы можем воспользоваться концепцией «первым вошел, первым вышел» (first-in-first-out, FIFO) из очереди (queue). Мы помещаем в очередь сначала ближайшую к нам вершину, затем ее непосещенных соседей, и продолжаем этот процесс, пока очередь не опустеет или пока мы не найдем искомую вершину.

Вот код:

// при условии, что мы имеем дело со смежным списком
// например, таким: adj = {A:[B,C,D], B:[E,F], ... }
function bfs(adj, s, t) {
	// adj - смежный список
	// s - начальная вершина
	// t - пункт назначения

	// инициализируем очередь
	let queue = []
	// добавляем s в очередь
	queue.push(s)
	// помечаем s как посещенную вершину во избежание повторного добавления в очередь
	s.visited = true
	while(queue.length > 0) {
		// удаляем первый (верхний) элемент из очереди
		let v = queue.shift()
		// abj[v] - соседи v
		for(let neighbor of adj[v]) {
			// если сосед не посещался
			if(!neighbor.visited) {
				// добавляем его в очередь
				queue.push(neighbor)
				// помечаем вершину как посещенную
				neighbor.visited = true
				// если сосед является пунктом назначения, мы победили
				if(neighbor === t) return true
			}
		} 
	}
	// если t не обнаружено, значит пункта назначения достичь невозможно
	return false
}

Анализ BFS

Может показаться, что BFS работает медленнее. Однако если внимательно присмотреться к визуализациям, можно увидеть, что они имеют одинаковое время выполнения.

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

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

Таким образом, время выполнения BFS также составляет O(V + E), а поскольку мы используем очередь, вмещающую все вершины, его пространственная сложность составляет O(V).

Аналогии из реальной жизни

Если приводить аналогии из реальной жизни, то вот как я представляю себе работу DFS и BFS.

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

Упрощенная версия выглядит так:

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

Упрощенная версия выглядит так:

Выводы

• Поиск в глубину и поиск в ширину используются для обхода графа.
• DFS двигается по граням туда и обратно, а BFS распространяется по соседям в поисках цели.
• DFS использует стек, а BFS — очередь.
• Время выполнения обоих составляет O(V + E), а пространственная сложность — O(V).
• Данные алгоритмы имеют разную философию, но одинаково важны для работы с графами.

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

Благодарю за внимание.

Обход в ширину (Поиск в ширину, англ. BFS, Breadth-first search) — один из простейших алгоритмов обхода графа, являющийся основой для многих важных алгоритмов для работы с графами.

Описание алгоритма

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

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

Анализ времени работы

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

Корректность

Дерево обхода в ширину

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

Реализация

Предложенная ниже функция возвращает кратчайшее расстояние между двумя вершинами.

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

int BFS(G: (V, E), source: int, destination: int):
    d = int[|V|]
    fill(d, )
    d[source] = 0
    Q = 
    Q.push(source)
    while Q  
        u = Q.pop()
        for v: (u, v) in E
            if d[v] == 
                d[v] = d[u] + 1
                Q.push(v)
    return d[destination]

Если требуется найти расстояние лишь между двумя вершинами, из функции можно выйти, как только будет установлено значение .
Еще одна оптимизация может быть проведена при помощи метода meet-in-the-middle.

Вариации алгоритма

0-1 BFS

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

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

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

1-k BFS

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

См. также

• Обход в глубину, цвета вершин
• Алгоритм Дейкстры
• Теория графов

Источники информации

• Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ — 2-е изд. — М.: «Вильямс», 2007. — с. 459. — ISBN 5-8489-0857-4
• MAXimal :: algo :: Поиск в ширину
• Wikipedia — Breadth-first search
• Wikipedia — Поиск в ширину
• Визуализатор алгоритма