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