322
правки
Изменения
→Алгоритм
Пусть <tex>G_0 = (V_0, E_0)</tex> - исходный граф.<br>
1) Если хотя бы одна вершина графа <tex>G_0</tex> недостижима из <tex>v</tex>, то требуемое дерево построить нельзя.<br>
2) Для каждой вершины <tex>u\ne v</tex> графа <tex>G_0</tex>, в которую входит хотя бы одно ребро, произведём следующую операцию: найдём ребро минимального веса, входящее в <tex>u</tex> и вычтем его вес из весов всех рёбер, входящих в <tex>u</tex>. <tex>m(u) = \min \limits_{v \in V_0}w(vu), w'(vu) = w(vu) - m(u)</tex>.<br>
3) Строим граф <tex>K = (V_0,K_0)</tex>, где <tex>K_0</tex> - множество рёбер нулевого веса графа <tex>G_0</tex> c весовой функцией <tex>w'</tex>. Если в этом графе найдётся остовное дерево с корнем в <tex>v</tex>, то оно и будет искомым.<br>
4) Если такого дерева нет, то построим граф <tex>C</tex> - конденсацию графа <tex>K</tex>. Пусть <tex>y</tex> и <tex>z</tex> - две вершины графа <tex>C</tex>, отвечающие компонентам сильной связности <tex>Y</tex> и <tex>Z</tex> графа <tex>K</tex> соответственно. Положим вес ребра между вершинами <tex>y</tex> и <tex>z</tex> равным минимальному среди весов рёбер графа <tex>G_0</tex> с весовой функцией <tex>w'</tex>, идущих из <tex>Y</tex> в <tex>Z</tex>.<br>
