Сложность времени выполнения BFS для несвязанного и косвенного графа

Question

Я знаю, что для связного косвенного графа время выполнения для BFS равно O (V + E).Но что, если график не связан?Затем я предполагаю, что нам нужно запустить цикл, чтобы сначала проверить состояние каждой вершины (посещено или нет).

Вот простой qseudocode для моей идеи.Предположим, что каждая вершина имеет белый цвет как признак непосещения в начале.Серый, как посетил, черный, как принято.

// BFS для неподключенного косвенного графа

BFS(G):   
for each v in G:
    if (v.color is white) do:
        v.color = gray;
        enqueue(Q, v);
        while Q is not empty do:
            u = dequeue(Q);
            while s is adjacent to u has color white
                  s.color = gray;
                  enqueue(Q,s);
            u.color = black;

Это мое предположение qseudocode для неподключенного косвенного графа.У меня есть проблемы, чтобы выяснить время выполнения.Я думаю, что это все еще O (V + E), но я не могу дать разумное объяснение.

Могу ли я узнать, как уточнить время работы этого qseudocode?Или, если мой qseudocode неэффективен, пожалуйста, дайте мне знать эффективный.

Спасибо!

Answer 1

Да, временная сложность все еще O(V + E).

Просто проверьте каждый цикл и максимальное количество раз, которое он может выполняться.

Внешний цикл будет иметь O(V) шагов.

Очередь проверки цикла также будет иметь O(V) шагов, поскольку каждый узел в графике вставляется в очередь только один раз (когда он был окрашен в белый цвет).

Сложная частьтретий цикл проверки соседних узлов u.Обратите внимание, что мы уже установили, что u будет представлять каждый узел на графике ровно один раз.Если вы используете список смежности для представления графа, этот шаг займет O(E) времени.

Общая сложность времени: O(V + E).

Answer 2

Да, вы правы.Внешний цикл повторяется по всем вершинам не более одного раза, поэтому он находится в O(|V|).Внутренняя часть - это BFS для связанных графов, то есть O(|V|+|E|).Затем в целом он остается в O(|V|+|E|), так как вы смотрите на каждую вершину и каждое ребро не более O(1) раз.

В качестве более общего объяснения, в графе у вас есть линейное число вершин, но вы можетеиметь квадратичное число ребер, подумайте о полном графе .Таким образом, если граф отключен, у вас просто меньше ребер для прохождения.