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

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

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

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

Алгоритм

Опис

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

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

Реалізація

Позначення:

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

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

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

Складність

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

Джерела

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