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




№ 2/6 BFS

Read Theory

БФС (поиск в ширину, 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;
}
Your last submission is saved in the editor window.
     

Results:

All results:

©2009 - 2019 SilverTests.ru/en

Education

Quizes
Problems
Courses

My Account

Register
Sign

About us

Contacts
Rules