Противостояние Cormen Wrestler BFS

Question

В вопросе 22.2.6 Cormen у нас проблема борца. Там, где говорится, есть N борец i.e N узлов и r пар для соперничества, то есть ребра, и нам нужно разделить борца на хороших и плохих парней, чтобы не было двух хороших парней.

Решение дано это

Выполните столько BFSS по мере необходимости, чтобы посетить все вершины. Назначьте всех борцов, чья дистанция - это даже хорошие ребята, и все борцы, чья дальность нечетна, являются плохими. ребята. Затем проверьте каждый край, чтобы убедиться, что он идет между хорошим парнем и плохим парнем . Это решение потребовало бы времени O (n + r) для времени BFS, O (n), чтобы назначить каждому борец в качестве хорошего парня или плохого парня и время O (r) для проверки краев, которое равно O (n + r) общее время.

У меня есть несколько вопросов по поводу решения

Perform столько BFSS, сколько необходимо, чтобы посетить все вершины. -> Начиная с разных узлов каждый раз? Но они будут давать нам одно и то же связующее дерево каждый раз?

насчет узлов, которые не достижимы из BFS

Answer 1

Да, как @ N.m уже упоминалось. вам может быть предоставлен график G, который может быть не подключен. Для примера рассмотрим этот график

У вас есть 2 компоненты связности. Если вы запустите BFS (или DFS) только с node1, вы никогда не узнаете node3, node4, node5. Следовательно, выполняя BFS с каждого узла, вы обнаружите все связанные компоненты. Это также дает вам ответ на вопрос, что выполнение BFS из каждого узла не приведет к тому же остовному дереву. Следовательно, сложность O(n + e) для n узлов и e ребер.

---

Примечания - этот график не может быть правильным для вашей постановки задачи, как вы упомянули N узлы и г пар, т.е. без каких-либо нечетных узлов в любом компоненте связности. Это изображение было использовано для объяснения связанных компонентов.