Алгоритм двох китайців — алгоритм побудови мінімального кістякового дерева в підвішеному орієнтованому графі з коренем в заданій вершині. Був розроблений математиками Чу Йонджіном і Лю Цзенхонгом.
Постановка задачі Задано зважений орієнтований граф і початкова вершина . Потрібно побудувати кореневе остовне дерево в з коренем у вершині , сума ваг усіх ребер якого мінімальна.
Алгоритм Опис Якщо хоча б одна вершина графу недосяжна з , то необхідне дерево побудувати не можна.
Для кожної вершини графу зробимо таку операцію: знайдемо ребро мінімальної ваги, що входить до , і віднімемо вагу цього ребра з ваг всіх ребер, що входять до . . Будуємо граф , де — множина ребер нульової ваги графу з ваговою функцією . Якщо в цьому графі знайдеться кістякове дерево з коренем у , то воно і буде шуканим. Якщо такого дерева немає, то побудуємо граф — конденсацію графу . Нехай та — дві вершини графу , відповідаючі компонентам сильной зв'язності та графу відповідно. Покладемо вагу ребра між вершинами і рівною мінімальному серед ваг ребер графу з ваговою функцією , що ідуть з в . Продовжимо з пункту 2, використовуючи граф замість . У побудовано MST . Побудуємо тепер MST в з ваговою функцією . Додамо до всі вершини компоненти сильної зв'язності графу , якій належить (по шляхах нульового ваги з ). Нехай у є ребро , де відповідає компоненті сильної зв'язності , а - компоненті сильної зв'язності графу . Між і у графі з ваговою функцією є ребро , вага якого дорівнює вазі ребра . Додамо це ребро до дерева . Додамо до всі вершини компоненти по шляхах нульового ваги з . Зробимо так для кожного ребра дерева . Отримане дерево - 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