Алгоритмы и структуры данных

Алгоритм Краскала

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

Алгоритм:
1. Начните с пустого набора, представляющего минимальное связующее дерево (MST).
2. Отсортируйте все ребра графа в порядке возрастания веса.
3. Для каждого ребра проверьте, не приведет ли его добавление к MST к созданию цикла. Обычно это делается с использованием структуры данных с непересекающимися наборами. Если добавление ребра не образует цикл, добавьте его в MST.
4. Продолжайте процесс выбора ребер до тех пор, пока MST не будет содержать все вершины или пока не будут рассмотрены все ребра.
5. Алгоритм считается завершенным, когда MST содержит все вершины или когда все ребра учтены.

Сложность: O(E log E)

www.tgoop.com/the_algorithms/4598

5.4K viewsNov 10, 2023 at 09:00

Алгоритм Краскала

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

Алгоритм:
1. Начните с пустого набора, представляющего минимальное связующее дерево (MST).
2. Отсортируйте все ребра графа в порядке возрастания веса.
3. Для каждого ребра проверьте, не приведет ли его добавление к MST к созданию цикла. Обычно это делается с использованием структуры данных с непересекающимися наборами. Если добавление ребра не образует цикл, добавьте его в MST.
4. Продолжайте процесс выбора ребер до тех пор, пока MST не будет содержать все вершины или пока не будут рассмотрены все ребра.
5. Алгоритм считается завершенным, когда MST содержит все вершины или когда все ребра учтены.

Сложность: O(E log E)

BY Алгоритмы и структуры данных