BFS - BFS - обход в ширину

BFS - обход в ширину

БФС (поиск в ширину, breadth-first search) - способ обхода графа, очень часто применяется как в простых алгоритмах, так и в продвинутых. Поиск в ширину работает путём последовательного просмотра отдельных уровней графа, начиная с узла-источника, и постепенно удаляясь от него. Наглядно это показанно на анимации.

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

Формальное описание алгоритма:

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

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

Task

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

В первой строке вводятся 3 целых числа n, m, k(1 <= n <= 10^5, 0 <= m <= 10^5, 1 <= k <= n) - количество деревней, количество дорог между ними и номер деревни, в которой случился пожар.
В следующих m строках содержится по 2 числа u, v(1 <= u, v <= n) - номера двух деревень между которыми есть дорога. Индексация деревень ведется с 1.

Выведите одно число - за сколько дней сгорят все деревни.

Пример
Ввод:
6 7 1
1 2
1 5
2 3
5 4
3 4
3 6
4 6
Вывод
4

Python

Write a program below
#include<iostream> #include<vector> #include<queue> #include<algorithm> #include<cmath> using namespace std; vector<bool> used;//used[i] = true, если мы были в вершине i vector<vector<int> > g;//список смежности vector<int> tm;//tm[i] - день, когда подожглась деревня i int n, m, s; int bfs() {

} int main() { cin >> n >> m >> s; s--; g.resize(n); tm.resize(n); used.assign(n, false); for (int i = 0; i < m; i++) { int u, v; cin >> u >> v; u--, v--; g[u].push_back(v); g[v].push_back(u); } cout << bfs(); return 0; }

Write a program below

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#include<cmath>
using namespace std;
vector<bool> used;//used[i] = true, если мы были в вершине i
vector<vector<int> > g;//список смежности
vector<int> tm;//tm[i] - день, когда подожглась деревня i
int n, m, s;


int bfs()
{

}

int main()
{
	cin >> n >> m >> s;
	s--;
	g.resize(n);
	tm.resize(n);
	used.assign(n, false);
	for (int i = 0; i < m; i++)
	{
		int u, v;
		cin >> u >> v;
		u--, v--;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	cout << bfs();
        return 0;
}

Your last submission is saved in the editor window.

Results:

BFS - обход в ширину

All results:

Education

My Account

About us

BFS - обход в ширину

№ 2/6 BFS

All results:

Education

My Account

About us