Алгоритм поиска в ширину (BFS)
Представьте, что у нас есть граф с
n вершинами и e рёбрами, и нам нужно начать обход этого графа из одной вершины и постепенно посетить все вершины, которые можно достичь из начальной точки. Существует несколько способов сделать это, и одним из наиболее распространённых является алгоритм Breadth-First-Search (BFS). По своей природе BFS позволяет вычислять кратчайший путь от исходной вершины ко всем остальным в графе, что делает его крайне полезным во многих задачах.
Удобный способ представить себе работу BFS — это мыслительный образ с “поджиганием” графа и наблюдением за тем, как «огонь» распространяется. Представьте, что каждая вершина «горит» в течение 1 минуты, после чего огонь переходит к её ближайшим соседям. Каждый из них «горит» тоже 1 минуту и затем «зажигает» своих соседей и так далее.
То есть, вы “поджигаете” стартовую вершину. Затем огонь передаётся всем её соседям. Через минуту соседние вершины начинают «гореть» и, в свою очередь, «поджигают» свои соседние вершины. Этот процесс продолжается, пока не останется ни одной вершины, которую ещё можно «поджечь». Такой мысленный образ «сгорания» всего графа помогает при реализации BFS.
Реализовать BFS можно с помощью
queue (очереди) и списка вершин, которые уже были «зажжены» (то есть посещены), — used:from collections import deque
n, e = map(int, input().split()) # n: вершины, e: ребра
g = [[] for _ in range(n)] # graph - список смежности
for _ in range(e): # чтение ребер
a, b = map(int, input().split()) # a -> b и b -> a
g[a].append(b)
g[b].append(a)
start = int(input()) # стартовая вершина
used = [False] * n # вершины, которые уже посещены
q = deque([start]) # очередь с вершинами
used[start] = True # помечаем стартовую вершину как посещенную
while q: # пока очередь не пуста
v = q.popleft() # берем вершину из очереди
print(v, end=' ') # выводим вершину
for to in g[v]: # для каждой вершины, соединенной с v
if not used[to]: # если вершина не посещена
q.append(to) # добавляем вершину в очередь
used[to] = True # помечаем вершину как посещеннуюЗдесь мы сначала инициализируем граф и начинаем обход с вершины
start. Изначально все значения в used равны False. Когда мы посещаем вершину, мы добавляем её в очередь и отмечаем как посещённую. Это и есть «поджигание» графа. На каждом шаге мы добавляем в очередь все смежные вершины текущей вершины v, которые ещё не были посещены, и отмечаем их как использованные.Давайте посмотрим, как алгоритм будет выполняться для нескольких тестовых данных:
n = 4, e = 4
Входные данные
a, b таковы: [(0, 1), (0, 2), (1, 2), (3, 2)]Начальная вершина — 3
used = [False, False, False, True],q = [3]
v = 3,q = []→ в очередь добавляются все соседи, которые ещё не использовались
used = [False, False, True, True],q = [2]
v = 2,q = []→ в очередь добавляются все соседи, которые ещё не использовались
used = [True, True, True, True],q = [0, 1]
v = 0,q = [1]→ в очередь добавляются все соседи, которые ещё не использовались
v = 1,q = []→ в очередь добавляются все соседи, которые ещё не использовались
- Готово
n = 5, e = 4
Входные данные
a, b таковы: [(0, 1), (0, 2), (1, 2), (3, 4)]Начальная вершина — 0
used = [True, False, False, False, False],q = [0]
v = 0,q = []→ в очередь добавляются все соседи, которые ещё не использовались
used = [True, True, True, False, False],q = [1, 2]
v = 1,q = [2]→ в очередь добавляются все соседи, которые ещё не использовались
v = 2,q = []→ в очередь добавляются все соседи, которые ещё не использовались
- Готово
Notice how nodes 3 and 4 were never visited.
They were not connected to the initial node 0.
Задача: подсчитать количество компонент связности в графе
Дан неориентированный граф с
v вершинами и e рёбрами. Нужно вычислить, сколько в нём компонент связности. Набор вершин считается компонентой связности, если между любыми двумя вершинами в нём существует путь.Входные данные
В первой строке содержатся два числа
v (1 ≤ v ≤ 100 000) и e (1 ≤ e ≤ 100 000).Далее следует
e строк, каждая из которых содержит пару чисел v1, v2 (1 ≤ v1, v2 ≤ v). Это означает, что вершина v1 соединена с вершиной v2 и наоборот.Выходные данные
Программа должна вывести число компонент связности в графе.
Примеры
Входные данные | Выходные данные |
7 6
1 2
2 3
1 3
4 5
5 6
4 6 | 3 |
2 1
1 2 | 1 |
2 0 | 2 |
Constraints
Time limit: 3 seconds
Memory limit: 512 MB
Output limit: 1 MB