Алгоритм двух китайцев — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Исправление ошибки в псевдокоде)
(не показано 45 промежуточных версий 8 участников)
Строка 1: Строка 1:
Алгоритм двух китайцев строит минимальное остовное дерево во взвешенном ориентированном графе с корнем в определенной вершине. Был разработан математиками Чу Йонджином и Лю Цзенхонгом.
+
'''Алгоритм двух китайцев''' — алгоритм построения минимального остовного дерева во взвешенном ориентированном графе с корнем в заданной вершине. Был разработан математиками Чу Йонджином и Лю Цзенхонгом.
 +
 
 +
== Постановка задачи ==
 +
 
 +
Дан взвешенный ориентированный граф <tex>G(V, E)</tex> и начальная вершина <tex>v</tex>. Требуется построить корневое остовное дерево в <tex>G</tex> с корнем в вершине <tex>v</tex>, сумма весов всех ребер которого минимальна.
  
 
== Алгоритм ==
 
== Алгоритм ==
  
[[Файл:graph1.png|thumb|right|300x200px|Исходный граф <tex>G_0</tex>]]
 
[[Файл:graph2.png|thumb|right|300x200px|Граф <tex>C</tex>, построенный по графу <tex>G_0</tex>]]
 
  
=== Постановка задачи ===
+
=== Описание ===
  
Дан взвешенный ориентированный граф <tex>G(V, E)</tex> и начальная вершина <tex>v</tex>. Требуется построить корневое остовное дерево в <tex>G</tex> с корнем в вершине <tex>v</tex>, сумма весов всех ребер которого минимальна.
+
Если хотя бы одна вершина графа <tex>G</tex> недостижима из <tex>v</tex>, то требуемое дерево построить нельзя.
 +
 
 +
{|
 +
|-
 +
|width="70%"|
 +
# Для каждой вершины <tex>u \ne v</tex> графа <tex>G</tex> произведём следующую операцию: найдём ребро минимального веса, входящее в <tex>u</tex>, и вычтем вес этого ребра из весов всех рёбер, входящих в <tex>u</tex>. <tex>m(u) = \min \limits_{tu \in E}w(tu), w'(tu) = w(tu) - m(u)</tex>.<br>
 +
# Строим граф <tex>K = (V,K_0)</tex>, где <tex>K_0</tex> — множество рёбер нулевого веса графа <tex>G</tex> c весовой функцией <tex>w'</tex>. Если в этом графе найдётся остовное дерево с корнем в <tex>v</tex>, то оно и будет искомым.<br>
 +
# Если такого дерева нет, то построим граф <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</tex> с весовой функцией <tex>w'</tex>, идущих из <tex>Y</tex> в <tex>Z</tex>.<br>
 +
# Продолжим с пункта 2, используя граф <tex>C</tex> вместо <tex>G</tex>.<br>
 +
# В <tex>C</tex> построено MST <tex>T</tex>. Построим теперь MST <tex>T'</tex> в <tex>G</tex> с весовой функцией <tex>w'</tex>. Добавим к <tex>T'</tex> все вершины компоненты сильной связности графа <tex>K</tex>, которой принадлежит <tex>v</tex> (по путям нулевого веса из <tex>v</tex>). Пусть в <tex>T</tex> есть ребро <tex>yz</tex>, где <tex>y</tex> отвечает компоненте сильной связности <tex>Y</tex>, а <tex>z</tex> — компоненте сильной связности <tex>Z</tex> графа <tex>K</tex>. Между <tex>Y</tex> и <tex>Z</tex> в графе <tex>G</tex> с весовой функцией <tex>w'</tex> есть ребро <tex>y'z'</tex>, вес которого равен весу ребра <tex>yz</tex>. Добавим это ребро к дереву <tex>T'</tex>. Добавим к <tex>T'</tex> все вершины компоненты <tex>Z</tex> по путям нулевого веса из <tex>z'</tex>. Сделаем так для каждого ребра дерева <tex>T</tex>.<br>
 +
# Полученное дерево <tex>T'</tex> — MST в графе <tex>G</tex>.
 +
|
 +
|}
 +
 
 +
=== Пример ===
 +
 
 +
{| class = "wikitable" width="70%"
 +
|-
 +
! Описание !! Изображение
 +
|-
 +
|Исходный граф.
 +
|[[Файл:китайГраф1.png|200px]]
 +
|-
 +
|Произведем спуск до нулевых ребер (Фаза 1, 2).
 +
|[[Файл:китайГраф2.png|200px]]
 +
|-
 +
|По нулевым ребрам нельзя дойти до всех вершин из <tex>v</tex>, поэтому строим конденсацию и добавляем наименьшие ребра между компонентами (Фаза 3).
 +
Найдем <tex>MST</tex> для данного графа.
 +
|[[Файл:китайГраф3.png|200px]]
 +
|-
 +
|Произведем спуск до нулевых ребер (Фаза 1, 2).
 +
|[[Файл:китайГраф4.png|200px]]
 +
|-
 +
|По нулевым ребрам нельзя дойти до всех вершин из <tex>v</tex>, поэтому строим конденсацию и добавляем наименьшие ребра между компонентами (Фаза 3).
 +
Найдем <tex>MST</tex> для данного графа.
 +
|[[Файл:китайГраф5.png|200px]]
 +
|-
 +
|Произведем спуск до нулевых ребер (Фаза 1, 2). По полученным нулевым ребрам можно дойти из корня до всех вершин. Тогда запускаем <tex>dfs</tex> из корня и возвращаем ребра.
 +
|[[Файл:китайГраф6.png|200px]]
 +
|-
 +
|Находим корень в каждой из компонент, из каждого такого корня запускаем <tex>dfs</tex> по нулевым ребрам, возвращаем результат.
 +
|[[Файл:китайГраф7.png|200px]]
 +
|-
 +
|Находим корень в каждой из компонент, из каждого такого корня запускаем <tex>dfs</tex> по нулевым ребрам. Полученое дерево и есть <tex>MST</tex> в исходном графе.
 +
|[[Файл:китайГраф8.png|200px]]
 +
|}
 +
 
 +
=== Корректность ===
 +
 
 +
''' Замечания: '''
 +
* После перевзвешивания в каждую вершину кроме <tex>v</tex> входит по крайней мере одно ребро нулевого веса.<br>
 +
* Пусть <tex>T</tex> — искомое дерево в <tex>G</tex> с весовой функцией <tex>w</tex>. <tex>w'(T) = w(T) - \sum \limits_{u \in V \setminus v}m(u)</tex>, т.е. <tex>T</tex> - MST в <tex>G</tex> с весовой функцией <tex>w</tex> тогда и только тогда, когда <tex>T</tex> — MST в <tex>G</tex> с весовой функцией <tex>w'</tex>.<br>
 +
 
 +
{{Лемма
  
=== Описание ===
+
|statement=
 +
Кратчайшее дерево путей <tex>T'</tex> в графе <tex>G</tex> можно получить, найдя кратчайшее дерево путей <tex>T</tex> в графе <tex>C</tex>, а затем заменив в нем каждую компоненту сильной связности деревом, построенным из дуг нулевой длинны.
 +
|proof=
 +
Зафиксируем любое дерево путей и покажем, что в графе <tex>G</tex> найдется дерево не большей длины, имеющее такую структуру, как сказано в лемме. Для такой структуры дерева необходимо и достаточно, чтобы в каждое из подмножеств входило только по одному ребру. Меньше быть не может, иначе получится отдельная компонента связности. Если же в какое-то подмножество входит больше чем одно ребро, то все ребра кроме одного можно заменить ребрами нулевой длины, лежащими внутри подмножества, что разве лишь уменьшит длину дерева и не нарушит связности. Повторяя это преобразование нужное число раз мы добьемся искомой структуры дерева.
 +
}}
  
1) Если хотя бы одна вершина графа <tex>G</tex> недостижима из <tex>v</tex>, то требуемое дерево построить нельзя.<br>
+
Из сделанных замечаний и леммы следует, что дерево <tex>T'</tex> MST в <tex>G</tex>.
2) Для каждой вершины <tex>u \ne v</tex> графа <tex>G</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,K_0)</tex>, где <tex>K_0</tex> - множество рёбер нулевого веса графа <tex>G</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</tex> с весовой функцией <tex>w'</tex>, идущих из <tex>Y</tex> в <tex>Z</tex>.<br>
 
5) Продолжим с пункта 2, используя граф <tex>C</tex> вместо <tex>G</tex>.<br>
 
6) В <tex>C</tex> построено MST <tex>T</tex>. Построим теперь MST <tex>T'</tex> в <tex>G</tex> с весовой функцией <tex>w'</tex>. Добавим к <tex>T'</tex> все вершины компоненты сильной связности графа <tex>K</tex>, которой принадлежит <tex>v</tex> (по нулевым путям из <tex>v</tex>). Пусть в <tex>T</tex> есть ребро <tex>yz</tex>, <tex>y</tex> отвечает компоненте сильной связности <tex>Y</tex>, а <tex>z</tex> - компоненте сильной связности <tex>Z</tex> графа <tex>K</tex>. Между <tex>Y</tex> и <tex>Z</tex> в графе <tex>G</tex> с весовой функцией <tex>w'</tex> есть ребро <tex>y'z'</tex>, вес которого равен весу ребра <tex>yz</tex>. Добавим это ребро к дереву <tex>T'</tex>. Добавим к <tex>T'</tex> все вершины компоненты <tex>Z</tex> по нулевым путям из <tex>z'</tex>. Сделаем так для каждого ребра дерева <tex>T</tex>.<br>
 
7) Полученное дерево <tex>T'</tex> - MST в графе <tex>G</tex>.
 
  
== Корректность ==
+
=== Реализация ===
  
1) После перевзвешивания в каждую вершину, кроме <tex>v</tex>, входит по крайней мере 1 ребро нулевого веса.<br>
+
Обозначения:
2) Пусть <tex>T</tex> - искомое дерево в <tex>G</tex> с весовой функцией <tex>w</tex>. <tex>w'(T) = w(T) - \sum \limits_{u \in V_0 \setminus v}m(u)</tex>, т.е. <tex>T</tex> - MST в <tex>G</tex> с весовой функцией <tex>w</tex> тогда и только тогда, когда <tex>T</tex> - MST в <tex>G</tex> с весовой функцией <tex>w'</tex>.<br>
+
*Граф хранится в виде множества ребер + индекс корня.
3) Пусть есть некоторый путь от вершины <tex>v</tex> до некоторой вершины <tex>u</tex> в графе <tex>G</tex> с весовой функцией <tex>w'</tex>. Тогда мы можем добавить к нашему дереву все вершины из компоненты сильной связности графа <tex>K</tex>, которой принадлежит вершина <tex>u</tex> (по нулевым путям из <tex>u</tex>). При этом вес нашего дерева не изменится.<br>
+
*Множество ребер - список смежности.
4) Если в графе <tex>K</tex> нет остовного дерева с корнем в <tex>v</tex>, то в графе <tex>C</tex> содержится меньше вершин, чем в графе <tex>G</tex>. Иначе, если бы в <tex>C</tex> было бы столько же вершин, сколько в <tex>G</tex>, то в <tex>K</tex> все компоненты сильной связности состояли бы из единственной вершины. Значит в <tex>G</tex> с весовой функцией <tex>w'</tex> не было бы нулевых циклов. То есть мы смогли бы построить в <tex>K</tex> остовное дерево с корнем в <tex>v</tex>, что противоречит нашему предположению.<br>
+
*Ребро - структура {from, to, weight}.
5) Из сделанных замечаний следует, что дерево <tex>T'</tex> - MST в <tex>G</tex>.
+
*root - текущий корень.
 +
 +
Особенность реализации: алгоритму не важна кратность ребер, поэтому при составлении нового графа кратные ребра могут
 +
появиться - это уменьшает асимптотику с <tex>O(V^2)</tex> до <tex>O(E)</tex>  
 +
 +
Проверяем, можно ли дойти из <tex>v</tex> до остальных вершин. Если можно - запускаем findMST.
 +
 +
int findMST(edges, n, root):
 +
    int res = 0
 +
    int minEdge[n] // создаем массив минимумов, входящих в каждую компоненту, инициализируем бесконечностью.
 +
    for each <tex>e \in </tex> edges
 +
        minEdge[e.to] = min(e.w, minEdge[e.to])
 +
    for each <tex>v \in V \backslash \{root\}</tex>
 +
        res += minEdge[v] //веса минимальных ребер точно будут в результате
 +
    edge zeroEdges[] //создаем массив нулевых ребер
 +
    for each <tex>e \in </tex> edges
 +
        if e.w == minEdge[e.to]
 +
            zeroEdges.pushback(<tex>e_1</tex>) // <tex>e_1</tex> - ребро е, уменьшенное на минимальный вес, входящий в e.to
 +
    if dfs(root, zeroEdges) // проверяем, можно ли дойти до всех вершин по нулевым ребрам
 +
        return res
 +
    int newComponents[n] // будущие компоненты связности
 +
    newComponents = Сondensation(zeroEdges)
 +
    edge newEdges[] //создаем массив ребер в новом графе с вершинами в полученных компонентах
 +
    for each <tex>e \in</tex> edges
 +
        if e.to и e.from в разных компонентах
 +
            добавляем в newEdges ребро с концами в данных компонентах и весом e.w - minEdge[e.to]
 +
    res += findMST(newEdges, ComponentsCount, newComponents[root])
 +
    return res
  
== Сложность ==
+
=== Сложность ===
Всего будет построено не более <tex>|V|</tex> конденсаций. Конденсацию можно построить за <tex>O(|E|)</tex>. Значит алгоритм можно реализовать за <tex>O(|V||E|)</tex>.
+
Всего будет построено не более <tex>V</tex> конденсаций. Конденсацию можно построить за <tex>O(E)</tex>. Значит, алгоритм можно реализовать за <tex>O(VE)</tex>.
  
 
== Источники ==
 
== Источники ==
 
*Романовский И. В. '''Дискретный анализ''', 3-е изд., перераб. и доп. - СПб.:Невский Диалект; БХВ-Петербург, 2003. - 320 с.: ил. - '''ISBN 5-7940-0114-3'''
 
*Романовский И. В. '''Дискретный анализ''', 3-е изд., перераб. и доп. - СПб.:Невский Диалект; БХВ-Петербург, 2003. - 320 с.: ил. - '''ISBN 5-7940-0114-3'''
 
* [http://is.ifmo.ru/vis/ctree/ http://is.ifmo.ru]
 
* [http://is.ifmo.ru/vis/ctree/ http://is.ifmo.ru]
 +
 +
==См. также==
 +
* [[Алгоритм Борувки]]
 +
* [http://en.wikipedia.org/wiki/Edmonds%27_algorithm Edmonds' Algorithm]
 +
* [http://rain.ifmo.ru/cat/view.php/vis/graph-spanning-trees/shortest-tree-chinese-2003 Визуализатор алгоритма]
  
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Остовные деревья ]]
 
[[Категория: Остовные деревья ]]

Версия 02:47, 5 апреля 2018

Алгоритм двух китайцев — алгоритм построения минимального остовного дерева во взвешенном ориентированном графе с корнем в заданной вершине. Был разработан математиками Чу Йонджином и Лю Цзенхонгом.

Постановка задачи

Дан взвешенный ориентированный граф [math]G(V, E)[/math] и начальная вершина [math]v[/math]. Требуется построить корневое остовное дерево в [math]G[/math] с корнем в вершине [math]v[/math], сумма весов всех ребер которого минимальна.

Алгоритм

Описание

Если хотя бы одна вершина графа [math]G[/math] недостижима из [math]v[/math], то требуемое дерево построить нельзя.

  1. Для каждой вершины [math]u \ne v[/math] графа [math]G[/math] произведём следующую операцию: найдём ребро минимального веса, входящее в [math]u[/math], и вычтем вес этого ребра из весов всех рёбер, входящих в [math]u[/math]. [math]m(u) = \min \limits_{tu \in E}w(tu), w'(tu) = w(tu) - m(u)[/math].
  2. Строим граф [math]K = (V,K_0)[/math], где [math]K_0[/math] — множество рёбер нулевого веса графа [math]G[/math] c весовой функцией [math]w'[/math]. Если в этом графе найдётся остовное дерево с корнем в [math]v[/math], то оно и будет искомым.
  3. Если такого дерева нет, то построим граф [math]C[/math] — конденсацию графа [math]K[/math]. Пусть [math]y[/math] и [math]z[/math] — две вершины графа [math]C[/math], отвечающие компонентам сильной связности [math]Y[/math] и [math]Z[/math] графа [math]K[/math] соответственно. Положим вес ребра между вершинами [math]y[/math] и [math]z[/math] равным минимальному среди весов рёбер графа [math]G[/math] с весовой функцией [math]w'[/math], идущих из [math]Y[/math] в [math]Z[/math].
  4. Продолжим с пункта 2, используя граф [math]C[/math] вместо [math]G[/math].
  5. В [math]C[/math] построено MST [math]T[/math]. Построим теперь MST [math]T'[/math] в [math]G[/math] с весовой функцией [math]w'[/math]. Добавим к [math]T'[/math] все вершины компоненты сильной связности графа [math]K[/math], которой принадлежит [math]v[/math] (по путям нулевого веса из [math]v[/math]). Пусть в [math]T[/math] есть ребро [math]yz[/math], где [math]y[/math] отвечает компоненте сильной связности [math]Y[/math], а [math]z[/math] — компоненте сильной связности [math]Z[/math] графа [math]K[/math]. Между [math]Y[/math] и [math]Z[/math] в графе [math]G[/math] с весовой функцией [math]w'[/math] есть ребро [math]y'z'[/math], вес которого равен весу ребра [math]yz[/math]. Добавим это ребро к дереву [math]T'[/math]. Добавим к [math]T'[/math] все вершины компоненты [math]Z[/math] по путям нулевого веса из [math]z'[/math]. Сделаем так для каждого ребра дерева [math]T[/math].
  6. Полученное дерево [math]T'[/math] — MST в графе [math]G[/math].

Пример

Описание Изображение
Исходный граф. КитайГраф1.png
Произведем спуск до нулевых ребер (Фаза 1, 2). КитайГраф2.png
По нулевым ребрам нельзя дойти до всех вершин из [math]v[/math], поэтому строим конденсацию и добавляем наименьшие ребра между компонентами (Фаза 3).

Найдем [math]MST[/math] для данного графа.

КитайГраф3.png
Произведем спуск до нулевых ребер (Фаза 1, 2). КитайГраф4.png
По нулевым ребрам нельзя дойти до всех вершин из [math]v[/math], поэтому строим конденсацию и добавляем наименьшие ребра между компонентами (Фаза 3).

Найдем [math]MST[/math] для данного графа.

КитайГраф5.png
Произведем спуск до нулевых ребер (Фаза 1, 2). По полученным нулевым ребрам можно дойти из корня до всех вершин. Тогда запускаем [math]dfs[/math] из корня и возвращаем ребра. КитайГраф6.png
Находим корень в каждой из компонент, из каждого такого корня запускаем [math]dfs[/math] по нулевым ребрам, возвращаем результат. КитайГраф7.png
Находим корень в каждой из компонент, из каждого такого корня запускаем [math]dfs[/math] по нулевым ребрам. Полученое дерево и есть [math]MST[/math] в исходном графе. КитайГраф8.png

Корректность

Замечания:

  • После перевзвешивания в каждую вершину кроме [math]v[/math] входит по крайней мере одно ребро нулевого веса.
  • Пусть [math]T[/math] — искомое дерево в [math]G[/math] с весовой функцией [math]w[/math]. [math]w'(T) = w(T) - \sum \limits_{u \in V \setminus v}m(u)[/math], т.е. [math]T[/math] - MST в [math]G[/math] с весовой функцией [math]w[/math] тогда и только тогда, когда [math]T[/math] — MST в [math]G[/math] с весовой функцией [math]w'[/math].
Лемма:
Кратчайшее дерево путей [math]T'[/math] в графе [math]G[/math] можно получить, найдя кратчайшее дерево путей [math]T[/math] в графе [math]C[/math], а затем заменив в нем каждую компоненту сильной связности деревом, построенным из дуг нулевой длинны.
Доказательство:
[math]\triangleright[/math]
Зафиксируем любое дерево путей и покажем, что в графе [math]G[/math] найдется дерево не большей длины, имеющее такую структуру, как сказано в лемме. Для такой структуры дерева необходимо и достаточно, чтобы в каждое из подмножеств входило только по одному ребру. Меньше быть не может, иначе получится отдельная компонента связности. Если же в какое-то подмножество входит больше чем одно ребро, то все ребра кроме одного можно заменить ребрами нулевой длины, лежащими внутри подмножества, что разве лишь уменьшит длину дерева и не нарушит связности. Повторяя это преобразование нужное число раз мы добьемся искомой структуры дерева.
[math]\triangleleft[/math]

Из сделанных замечаний и леммы следует, что дерево [math]T'[/math] — MST в [math]G[/math].

Реализация

Обозначения:

  • Граф хранится в виде множества ребер + индекс корня.
  • Множество ребер - список смежности.
  • Ребро - структура {from, to, weight}.
  • root - текущий корень.

Особенность реализации: алгоритму не важна кратность ребер, поэтому при составлении нового графа кратные ребра могут появиться - это уменьшает асимптотику с [math]O(V^2)[/math] до [math]O(E)[/math]

Проверяем, можно ли дойти из [math]v[/math] до остальных вершин. Если можно - запускаем findMST.

int findMST(edges, n, root):
   int res = 0
   int minEdge[n] // создаем массив минимумов, входящих в каждую компоненту, инициализируем бесконечностью.
   for each [math]e \in [/math] edges
       minEdge[e.to] = min(e.w, minEdge[e.to])
   for each [math]v \in V \backslash \{root\}[/math]
       res += minEdge[v] //веса минимальных ребер точно будут в результате
   edge zeroEdges[] //создаем массив нулевых ребер
   for each [math]e \in [/math] edges
       if e.w == minEdge[e.to]
           zeroEdges.pushback([math]e_1[/math]) // [math]e_1[/math] - ребро е, уменьшенное на минимальный вес, входящий в e.to
   if dfs(root, zeroEdges) // проверяем, можно ли дойти до всех вершин по нулевым ребрам
       return res
   int newComponents[n] // будущие компоненты связности
   newComponents = Сondensation(zeroEdges) 
   edge newEdges[] //создаем массив ребер в новом графе с вершинами в полученных компонентах
   for each [math]e \in[/math] edges
       if e.to и e.from в разных компонентах
           добавляем в newEdges ребро с концами в данных компонентах и весом e.w - minEdge[e.to]
   res += findMST(newEdges, ComponentsCount, newComponents[root])
   return res

Сложность

Всего будет построено не более [math]V[/math] конденсаций. Конденсацию можно построить за [math]O(E)[/math]. Значит, алгоритм можно реализовать за [math]O(VE)[/math].

Источники

  • Романовский И. В. Дискретный анализ, 3-е изд., перераб. и доп. - СПб.:Невский Диалект; БХВ-Петербург, 2003. - 320 с.: ил. - ISBN 5-7940-0114-3
  • http://is.ifmo.ru

См. также