Зачем говорить, что поиск в ширину выполняется во времени
Часто утверждается (например, в Википедии ), что время выполнения поиска в ширину (BFS) на графе G=(V,E)G=(V,E)G=(V,E) равно O(|V|+|E|)O(|V|+|E|)O(|V|+|E|) . Тем не менее, любой связный граф имеет |V|≤|E|+1|V|≤|E|+1|V|\leq |E|+1 , и даже в несвязном графе, BFS никогда не будет смотреть на вершинах...