Алгоритм двох китайців

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

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

Задано зважений орієнтований граф $G(V,E)$ і початкова вершина $v$. Потрібно побудувати кореневе остовне дерево в $G$ з коренем у вершині $v$, сума ваг усіх ребер якого мінімальна.

Алгоритм

Опис

Якщо хоча б одна вершина графу $G$ недосяжна з $v$, то необхідне дерево побудувати не можна.

Для кожної вершини $u\neq v$ графу $G$ зробимо таку операцію: знайдемо ребро мінімальної ваги, що входить до $u$, і віднімемо вагу цього ребра з ваг всіх ребер, що входять до $u$. $m(u)=\min \limits _{tu\in E}w(tu),w'(tu)=w(tu)-m(u)$. Будуємо граф $K=(V,K_{0})$, де $K_{0}$ — множина ребер нульової ваги графу $G$ з ваговою функцією $w'$. Якщо в цьому графі знайдеться кістякове дерево з коренем у $v$, то воно і буде шуканим. Якщо такого дерева немає, то побудуємо граф $C$ — конденсацію графу $K$. Нехай $y$ та $z$ — дві вершини графу $C$, відповідаючі компонентам сильной зв'язності $Y$ та $Z$ графу $K$ відповідно. Покладемо вагу ребра між вершинами $y$ і $z$ рівною мінімальному серед ваг ребер графу $G$ з ваговою функцією $w'$, що ідуть з $Y$ в $Z$. Продовжимо з пункту 2, використовуючи граф $C$ замість $G$. У $C$ побудовано MST $T$. Побудуємо тепер MST $T'$ в $G$ з ваговою функцією $w'$. Додамо до $T'$ всі вершини компоненти сильної зв'язності графу $K$, якій належить $v$ (по шляхах нульового ваги з $v$ ). Нехай у $T$ є ребро $yz$, де $y$ відповідає компоненті сильної зв'язності $Y$, а $z$ - компоненті сильної зв'язності $Z$ графу $K$. Між $Y$ і $Z$ у графі $G$ з ваговою функцією $w'$ є ребро $y'z'$, вага якого дорівнює вазі ребра $yz$. Додамо це ребро до дерева $T'$. Додамо до $T'$ всі вершини компоненти $Z$ по шляхах нульового ваги з $z'$. Зробимо так для кожного ребра дерева $T$. Отримане дерево $T'$ - MST в графі $G$.

Реалізація

Позначення:

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

Особливість реалізації: алгоритмом не важлива кратність ребер, тому при складанні нового графу кратні ребра можуть з'явитися - це зменшує асимптотику з $O(V^{2})$ до $O(E)$

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

Складність

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

Джерела

• Романовский И. В. Дискретный анализ, 3-е изд., перераб. и доп. - СПб.:Невский Диалект; БХВ-Петербург, 2003. - 320 с.: ил. (233 страница) - ISBN 5-7940-0114-3
• http://is.ifmo.ru [Архівовано 20 квітня 2014 у Wayback Machine.]