Поиск в случайном порядке?

Два наиболее распространенных способа обхода графа - это поиск в ширину и глубина -первый поиск . Оба этих алгоритма поиска следуют общему шаблону:

• Создайте рабочий список W, заполненный начальным узлом s.
• Пока рабочий список не пустой:
  • Удалить первый элемент рабочего списка; назовите это v.
  • Если v не посещается:
    • Отметить v как посещенное.
    • Для каждого узла u, напрямую подключенного к v, добавьте u к W.

При поиске в ширину рабочий список W реализован как очередь FIFO , тогда как при поиске в глубину он стек LIFO . Если W является приоритетной очередью , вы получите поиск с равномерной стоимостью .

Некоторое время назад я задал вопрос о структуре данных для выбора случайных элементов из пакета . Если вы реализуете вышеуказанный рабочий список W с использованием этого случайного пакета, то вы получите алгоритм «случайный первый поиск», который случайным образом исследует узлы в графе, начиная с начального узла.

У меня такой вопрос: существуют ли какие-либо известные алгоритмы, использующие этот тип поиска? То есть есть ли алгоритмы, которые работают, генерируя таким образом случайное остовное дерево графа?