Найти максимальный вес ребра в графе G?

Question

Мое задание похоже на то, что с учетом V деревень, которые связаны с дорогами E на графике G, каждая дорога помечена положительным числом. И вам нужно хотя бы на уровне этого номера получить доступ к этой дороге. Другими словами, если дорога обозначена 5, то ваш уровень должен быть не менее 5 или более, чтобы получить доступ к этой дороге. Теперь мое задание попросить спроектировать алгоритм, найти минимальный уровень очистки, необходимый для того, чтобы можно было добраться до любой из деревень V из любой другой. Итак, моя интерпретация заключается в том, что мы можем просто найти край максимального веса на графике. Но я не выяснил, какой алгоритм подходит для этого условия.

Answer 1

Это можно решить за O(E).

Почему ваше решение неверно? Рассмотрим треугольник, где два ребра равны 1, а последний равен 2, наименьший необходимый зазор равен 1, ваше решение говорит 2.

Решение, которое я могу придумать, состоит в создании связующего дерева с минимальным узким местом (MBST), затем возьмите его максимальное преимущество, и это будет вашим уровнем допуска.

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

MBST может быть , созданным в O(E) с использованием деленияи победить методы, чем пройти через все ребра в этом дереве, чтобы найти максимум равен O(E). В общей сложности O(E).

Вы можете решить эту проблему с помощью простого MST, поскольку любое MST равно MBST ( доказательство в q3 ),но это займет O(E log V) или O(E + V log V), в зависимости от алгоритма ( Kruskal или Prim ).