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

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

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

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

Алгоритм

Опис

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

Для кожної вершини $u \neq v$ графу $G$ зробимо таку операцію: знайдемо ребро мінімальної ваги, що входить до $u$ , і віднімемо вагу цього ребра з ваг всіх ребер, що входять до $u$ . $m (u) = \min \limits_{t u \in E} w (t u), w^{'} (t u) = w (t u) - 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$ є ребро $y z$ , де $y$ відповідає компоненті сильної зв'язності $Y$ , а $z$ - компоненті сильної зв'язності $Z$ графу $K$ . Між $Y$ і $Z$ у графі $G$ з ваговою функцією $w^{'}$ є ребро $y^{'} z^{'}$ , вага якого дорівнює вазі ребра $y z$ . Додамо це ребро до дерева $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 ∖ {r o o t}$ 
       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 (V E)$ .

Джерела

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

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

Зміст

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