нахождения miniums расстояние между двумя подмножествами вершин

Question

Учитывая неориентированный граф G = (V, E), V1, V2 являются подмножествами V. d(V1,V2)=min d(v1,v2),
так что мне нужно, чтобы выяснить, как найти D (V1, V2), в O(|V|+|E|)

, если затем d(V1,V2)=0

в противном случае, я случайно выбрать v1' от V1 и запустить BFS (V1, v1 '), за исключением самой дальней вершины из v1' на v1 '' буду сделать то же для некоторой случайной вершины v2 'из V2. return d (V1, V2) = min {d (v1 ', v2'), d (v1 ', v2' '), d (v1''v2'), d (v1 '', v2 '')}

будет ли это работать? поскольку время выполнения BFS является O (| V | + | E |) предложенный алгоритм будет работать в O (| V | + | E |)

Answer 1

IMO, что вы можете сделать, это выглядит следующим образом:

1. Сканируйте набор V1 и отметьте все ребра, которые начинаются в узлах в V1 и заканчиваются в узлах, не входящих в V1.
2. Теперь объедините все узлы в V1 в один узел. Края, отмеченные на шаге 1, должны быть краями, выходящими из этого узла.
3. Сделайте то же самое для V2.
4. Теперь он сводится к кратчайшей проблеме маршрута между узлами V1 и V2. Это можно решить, проведя простую BFS на узле V1 или V2 в O (E), где E - число ребер в графе.