Еще одним алгоритмом обхода графа является поиск в ширину. Смотри также мою статью про обход в глубину: DFS.
Поиск в ширину обходит граф “по слоям”. Сначала начальную вершину, потом всех ее соседей. Потом всех соседей соседей и т.д.
Реализация обхода в ширину использует очередь.
Алгоритм следующий.
Помещаем начальную вершину в очередь. Помечаем ее как посещенную.
Пока очередь не пустая. Достаем вершину из очереди. Посещаем ее.
Для всех соседей, которые мы еще не посетили: помечаем их как посещенные и помещаем в очередь.
Реализация на Java:
void bfs(Node root) {
if (root == null) {
return;
}
Set<Node> visited = new HashSet<>();
Queue<Node> queue = new ArrayDeque<>();
queue.add(root);
visited.add(root);
while (!queue.isEmpty()) {
Node node = queue.poll();
visit(node);
for (Node neighbour : node.getNeighbours()) {
if (!visited.contains(neighbour)) {
visited.add(neighbour);
queue.add(neighbour);
}
}
}
}
Реализация на Python:
def bfs(root):
queue = []
visited = set()
queue.append(root)
visited.add(root)
while queue:
node = queue.pop(0)
visit(node)
for neighbour in node.neighbours:
if neighbour not in visited:
queue.append(neighbour)
visited.add(neighbour)
Давайте посмотрим как будет работать поиск в ширину на конкретном примере:
Зеленым я буду помечать уже посещенные вершины.
Вначале помещаем root в очередь и помечаем ее как посещенную:
Далее попадаем в цикл. Достаем из очереди 1. Посещаем ее. У нее 3 соседей: 2, 3, 4. Все они еще не посещенные. Помещаем их в очередь и помечаем их как посещенные.
На следующей итерации цикла достаем 2 из очереди. Посещаем ее. У нее соседи: 1, 5, 6. 1 уже посещена. Поэтому в очередь помещаем 5 и 6. Помечаем их как visited.
Далее достаем 3 из очереди. Посещаем ее. У нее соседи 1 и 7. 1 уже помечена как visited. Помещаем 7 в очередь и помечаем ее как visited.
Далее достаем 4 из очереди. Посещаем ее. У нее соседи 1, 8, 9, 10.
1 уже помечена как visited. Помечаем 8, 9, 10 и помещаем их в очередь.
Далее достаем 5. Посещаем ее. У нее соседи 2 и 11. 2 уже помечена. Помечаем 11 и помещаем в очередь.
Для всех оставшихся в очереди ситуция похожая. Достаем из очереди. Посещаем. Все соседи уже помечены, поэтому новые вершины в очередь не добавляем. И так до тех пор, пока очередь не будет пуста.
Top comments (0)