Алгоритм поиска связности графа

Question

Я занимаюсь интересным вопросом в программировании. Именно так: мы продолжаем добавлять ненаправленные ребра в граф, пока граф (или подграф) не соединится (т.е. мы можем использовать некоторый путь, чтобы добраться из каждой вершины в любую другую вершину в этом подграфе). Мы остановимся, как только график подключен. Например, если у нас есть вершины 1,2,3 и 4, и мы хотим, чтобы подграф 1,2,3 был связан. Допустим, у нас есть ребра (3,4), затем (2,3), затем (1,4), затем (1,3). Нам нужно только добавить первые 3 ребра для подключаемого подграфа, затем мы останавливаемся (ребро 1,3 не требуется). Очевидно, что я могу запускать BFS каждый раз, когда добавляется ребро, чтобы увидеть, сможем ли мы добраться до требуемых вершин, но если, скажем, m ребер, то нам, возможно, придется запускать BFS m раз, что кажется слишком медленным. Есть лучшие варианты? Спасибо.

Answer 1

Вы должны исследовать изумительную «структуру данных с несвязным множеством» и соответствующий алгоритм union - find. Это может показаться волшебным, но сложность времени и пространства в наихудшем случае крошечная, O (α (n)) и O (n) соответственно, где α - обратная функция Аккермана.

Answer 2

Я бы обычно делал это, используя несвязную структуру множеств, как предлагает Дуг. Это было бы похоже на алгоритм Крускала для нахождения минимального остовного дерева, за исключением того, что вы обрабатываете ребра в заданном порядке.

Если вам не требуется связующее дерево в качестве выходных данных, то вы можете сделать это с инкрементным BFS или DFS:

1. Выберите любую вершину и найдите связанные с ней вершины с помощью BFS или DFS. Цвет этих вершин красный. Конечно, если вы начнете без ребер, на этом этапе будет только одна красная вершина.
2. Когда вы добавляете ребра, больше ничего не делайте, пока не добавите ребро, которое соединяет красную вершину с не красная вершина. Затем запустите BFS или DFS, исключая новое ребро, чтобы найти все новые вершины, которые будут подключаться к красному набору. Покрасьте их все в красный цвет.
3. Остановитесь, когда все вершины будут красными.

На практике это немного проще, чем использование несвязного множества, и принимает O (| V | + | E | ) время, поскольку каждая вершина будет проходить ровно через один поиск BFS / DFS.

Тем не менее, он выполняет работу порциями, поэтому если вам нужно, чтобы каждый тест ребер был быстрым по отдельности , тогда лучше разделить множество.

Answer 3

Вы можете запустить BFS всего один раз, чтобы найти подключенные компоненты. Затем, каждый раз, когда вы добавляете ребро, если оно находится между вершинами двух разных компонентов, вы можете объединить их по ссылке. Таким образом, сложность этого алгоритма составляет |V| + |E|.

Обратите внимание, что реализация этого метода должна выполняться с помощью некоторых эталонных методов, особенно для обновления номера компонента вершин.