Алгоритмы графа

Question

Какое максимальное и минимальное количество ребер рассматривается в алгоритме кришука с примером для обоих случаев.

Что я думал, так как алгоритм Крушкаля заключается в поиске минимального остовного дерева, максимальное число ребер (V-1), где V - количество вершин. Добавление еще одного края приведет к циклу на графике. Как мы можем получить минимальное значение?

Answer 1

Дерево из N вершин всегда имеет края N-1. Следовательно, во время алгоритма Крускаля вы должны рассмотреть по крайней мере N-1 ребра. Примером может служить граф, являющийся деревом.

Answer 2

Алгоритм Kruskal останавливается, когда вы добавили V - 1 ребер к вашему MST, так что это минимум, который нужно учитывать. Это происходит, когда минимальное значение V - 1 ребер вашего графа не образует цикл, и они будут добавляться один за другим по алгоритму, после чего он остановится.

Например, рассмотрим полный граф с ребрами с стоимостью 1, что является минимальным на графике, между узлом 1 и каждым другим узлом. Сделать все остальные края стоимостью 2.

Худший случай - когда вы должны проверять каждый край (из которых есть O(V^2)), пока вы окончательно не выберете V - 1. Это означает, что вам нужно заставить много циклов создавать до того, как будет добавлен последний край.

Рассмотрите полный график снова. Нужно, чтобы ребра V - 2 между узлами 1 и V - 2 узлов стоили 1, что является минимальным на графике. Они будут выбраны первыми. Теперь позвольте узлу k быть тем, который не является частью выбранного края, так что он оставлен вне графика. Наибольшее значение имеют границы между узлом k и узлом 1. Это заставит его проверяться и добавляться к MST последнему, заставляя алгоритм проверять все края O(V^2) до создания MST.

Помните, что алгоритм Kruskal обрабатывает ребра в порядке возрастания их стоимости, отвергая ребра, которые формируют цикл, если они добавляются в MST, который мы строим.