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

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

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

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

Алгоритм

Опис

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

  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

Складність

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

Джерела

  • Романовский И. В. Дискретный анализ, 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.