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

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

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

ред.

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

Алгоритм

ред.

Опис

ред.

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

  1. Для кожної вершини   графу   зробимо таку операцію: знайдемо ребро мінімальної ваги, що входить до  , і віднімемо вагу цього ребра з ваг всіх ребер, що входять до  .  .
  2. Будуємо граф  , де   — множина ребер нульової ваги графу   з ваговою функцією  . Якщо в цьому графі знайдеться кістякове дерево з коренем у  , то воно і буде шуканим.
  3. Якщо такого дерева немає, то побудуємо граф   — конденсацію графу  . Нехай   та   — дві вершини графу  , відповідаючі компонентам сильной зв'язності   та   графу   відповідно. Покладемо вагу ребра між вершинами   і   рівною мінімальному серед ваг ребер графу   з ваговою функцією  , що ідуть з   в  .
  4. Продовжимо з пункту 2, використовуючи граф   замість  .
  5. У   побудовано MST  . Побудуємо тепер MST   в   з ваговою функцією  . Додамо до   всі вершини компоненти сильної зв'язності графу  , якій належить   (по шляхах нульового ваги з   ). Нехай у   є ребро  , де   відповідає компоненті сильної зв'язності  , а   - компоненті сильної зв'язності   графу  . Між   і   у графі   з ваговою функцією   є ребро  , вага якого дорівнює вазі ребра  . Додамо це ребро до дерева  . Додамо до   всі вершини компоненти   по шляхах нульового ваги з  . Зробимо так для кожного ребра дерева  .
  6. Отримане дерево   - MST в графі  .

Реалізація

ред.

Позначення:

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

Особливість реалізації: алгоритмом не важлива кратність ребер, тому при складанні нового графу кратні ребра можуть з'явитися - це зменшує асимптотику з   до  

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

Складність

ред.

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

Джерела

ред.