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

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

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

Задано зважений орієнтований граф $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

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.