Трохи про мінімальні кістяки

Підступні стрілочки

Типовий відвідувач сайту codeforces.com, напевно, знає, як шукати мінімальне (або навіть максимальне) остовне дерево (а то й остовний ліс). Вміє писати алгоритм Пріма, алгоритм Крускала. Дехто може бути навіть у курсі, що все це окремі випадки алгоритму Борувки, який у 1926 році розповідав, як оптимально електрифікувати Моравію (регіон Чехії). Ось тільки правильно працюють ці алгоритми виключно для неорієнтованих графів.

Нагадаю завдання. Даний зважений графG = (V, E, γ) (V - безліч вершин,E - безліч ребер або дуг,γ - Функція ваги на ребрах або дугах). Потрібно знайти підмножину ребер (дуг)S ⊆ E, таке, що:

У графі(V, S) не буде циклів (в орієнтованому випадку є додаткове обмеження: у кожну вершину має входити не більше однієї дуги зS ).
Серед таких максимальне включення: не можна додати ще одне ребро (дугу), щоб не зламалося попереднє обмеження. Зауважу, що з цього випливає глобальна максимальність за кількістю ребер (дуг).
Серед таких мінімальне за вагою:γ(S) = γ(e) слід мінімізувати.

У неорієнтованому графі досить було (алгоритм Крускала) брати ребра в порядку збільшення ваги, додавати до графа, якщо вони не утворюють цикл, інакше викидати. На жаль, у разі орієнтованого графа на нас чекає неприємний сюрприз.

На малюнку вище мінімальне кістякове дерево виділено і має вагу6, але після додавання двох дуг ваги1 таке стає недосяжним. Що ж робити?

Хитрі китайці

Як бути з орієнтованими графами світу розповіли 1965-го року два китайці: Чу Йонджин і ЛюЦзенхонґ. Незалежно від них приблизно в той же час (публікація у 1967 році) аналогічний алгоритм розробив Джек Едмондс. Завдання-то не дуже складна. Теж жадібність, просто трохи хитріша, ніж для неорієнтованого графа.

Для початку трохи визначимося із завданням. Є варіант, який я описував у «підступних стрілочках», коли відповідь — ліс кореневих дерев (те, що називають branching , «розгалуження»). А є варіант із виділеним коренем, тоді потрібно побудувати підвішене за цей корінь дерево мінімальної ваги (відповідно, arborescence, деревоподібне утворення). Перший варіант легко зводиться до другого: додамо в граф фіктивний корінь і намалюємо дугою нескінченної ваги в кожну вершину з цього кореня. Нескінченність, як завжди, слід підбирати акуратно, щоб з неї можна було щось повичитати, і після цього ще порівнювати.

Зведення у зворотний бік ще простіше: викинемо дуги, що йдуть у корінь (їх немає у правильній відповіді), після цього якщо існує arborescence , то оптимальний branching є і оптимальним arborescence5> теж. Пропоную вирішити завданняarborescence, тому що тоді зустрінеться менше неприємних випадків.

Чому б для якоїсь вершини не подивитися на всі дуги, що входять до неї. Якщо ми додамо (або віднімемо) якесь число до ваги цих дуг, то завдання не зміниться: у цю вершину у відповіді входить рівно одна дуга і вага відповіді зміниться рівно на це число. Віднімемо з мінімальної з них, що входять у вершину дуг вага.

Тепер у вершину приходить хоча б одна дуга ваги нуль, а ваги решти дуг невід'ємні. Звичайно, цю нульову дугу хочеться додати до відповіді. Що ж вийде, якщо провернути цю операцію з кожною (крім кореня) вершиною графа?

Графів виду «в кожну вершину приходить одна дуга» не так уже й багато. І, нагадаю, до однієї з вершин входить нуль дуг: корінь дерева. Може реалізуватися два варіанти: нудний та не дуже. У нудному варіанті всі вершини нульовими дугами зберуться в дерево, це й буде очевидним чином правильна відповідь. Але можуть і цикли.

Тут, до речі, важливо, що ми вичитали ваги дуг на вершині, а не просто взяли мінімальну. Сенс циклу з нульових дуг у тому, що можна прийти в будь-яку вершину циклу, і це автоматично дасть нам шлях до решти всіх вершин циклу. Тобто, якщо ми прийдемо у вершинуx, то просто замінимо нульову дугу, що веде доx за циклом, на дугу ззовні. За цю операцію нам доведеться заплатити різницею ваг дуг, тому, щоб на наступній ітерації вага дуги означала ціну його додавання, наведемо віднімання до нуля.

Відновлення відповіді

Не дуже хитре, якщо явно стискати граф (і зберігати конденсації з кожного зі стисків). Треба кожному циклі зрозуміти, яку дугу потрібно викинути. Підказка: ту, що приходить у вершину, відвідану дугою з верхнього рівня.

Якщо стискати не прості цикли, а компоненти сильної зв'язності, відновлювати буде трохи складніше. Прийде написати обхід у глибину, який по компоненті та першій відвіданій вершині видасть шляхи до решти.

Час роботи

У гіршому випадку може виявитися, що на кожному кроці сконденсується лише один цикл довжини два, тоді досягається час роботи Θ(n·m) , деn — кількість вершин у графі, аm - Кількість дуг.

Однак, якщо підійти до завдання трохи акуратніше, то можна вкластися в O(m log n + n²) , а то і в O (m log n) (або навіть в min (m log n, m + n²) , але це залишиться читачеві вякості вправи).

Тар'ян зміг, значить і ми впораємося

Нам знадобиться брухт, розібраний газотурбінний двигун та парочка структур даних. Роберт Тар'ян ще в 1977-му році написав статтю Finding Optimum Branchings

Загальна ідея

Звичайно, явно перебудовувати граф після кожного стиснення циклу ніхто не хоче. Просто треба працювати не з вершинами, а з їхніми групами (далі я називатиму їх «компонентами»). Зберігати їх можна в звичайній системі непересічних множин. Зручно віднести до окремої компоненти вершини, для яких вже знайшли відповідь («нульовий» шлях з кореня), разом із самим коренем.

Далі можна скористатися тим, що базовий алгоритм – жадібність. В якому порядку брати нульові дуги — не має значення, коректність від цього не змінюється, можна робити зручніше. Особисто мені зручніше взяти вершину і піти від неї в бік кореня. Тобто знайти мінімальну вхідну дугу, відняти, пройти по нулю, взяти мінімальну дугу, відняти, пройти, і так продовжувати.

Такий похід може закінчитися одним із двох варіантів. Перший: пройшовши по черговій дузі, потрапимо в компонент кореня (тобто, в сам корінь або в вершину, до якої вже є шлях з кореня). Він просто означає, що для вихідної вершини (і для всіх вершин на шляху) відповідь теж знайшлася, залишилося її відновити та об'єднати компоненти з кореневою.

Інший варіант засмутить фанатів гри «змійка», зате потішить древніх греків буквою ρ. Пройшовши дугою, потрапимо у вершину на шляху, яку ми нещодавно відвідували. Здрастуйте, цикл.

Саме цей цикл стиснути (тобто, об'єднати його компоненти в одну — пам'ятаємо, що стиснення виключно неявне). Це цілком можна зробити за розмір циклу (пройшовшись по ньому ще раз), післяпродовжити похід, але вже обробляючи колишній цикл як одну компоненту. Компонент у графі стало менше, значить рано чи пізно, стиснувши багато циклів, дістанемося до кореня.

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

Реалізація

Але для таких фокусів знадобиться друга структура даних: виколупувати мінімальну вхідну дугу з цілої компоненти треба швидко. У структурі слід зберігати безліч вхідних дуг (альтернативний варіант: заздалегідь відсортувати вхідні дуги кожної вершини і зберігати безліч вершин). Ми хочемо від структури даних наступне:

взяти мінімум
видалити мінімум (в альтернативному варіанті взяти наступну дугу в списку вершини, а в структурі даних зробити зміну одного значення)
додати число до всіх ваг
об'єднати дві структури в одну

Операція видалити мінімум потрібна з наступної причини. «Лінивий» стиск графа означає, що видаляти петлі (дуги всередині компоненти) ніхто не збирається. Тому операція «взяти мінімальну дугу, що входить у компоненту» цілком може повернути дугу, що виходить з тієї ж компоненти. У такому разі треба лише видалити цю дугу зі структури даних (кожну дугу графа доведеться видаляти не більше одного разу, час роботи не постраждав) і спробувати взяти мінімум ще раз.

Варіантів структури даних для такої справи є чимало. Декартове дерево за неявним ключем із випадковим пріоритетом, порахованим мінімумом на піддеревах та операцією на відрізку. Splay дерева при правильному підході. Якісь зливаються купи. Або хоча б пара з std::set та зсуву: підхід «при об'єднанні взятиелементи з меншого і по одному додати до більшого» дає перекидання кожного елемента не більше разів, щоправда, цей логарифм вилізе зайвий раз в асимптотиці часу роботи: .

Докладний розбір часу роботи теж залишу читачеві, цікавий залишився один момент.

Відновлення відповіді

Потрібно зрозуміти, які з дуг, взятих у процесі алгоритму, треба залишити, а які — видалити, щоб розімкнути цикли. Для цього треба пам'ятати, як ми стискали граф, інакше не вистачить інформації. На картинці два однакові графи, але якщо спочатку був стиснутий циклb →c →d, то разом зdb слід викинути дугуed, а якщо циклb →e →d, то дугуcd.

Більше того, дугиcd іed могли мати різну вагу до віднімання мінімумів, тому що обнулялися на різних кроках.

Це означає, що відновлення відповіді доведеться чесно спускатися вниз по компонентам. Для кожної компоненти, що з'являлася по ходу роботи алгоритму, запам'ятаємо, з яких компонент нижнього рівня вона складається, розгортати будемо рекурсивно. А от якщо ми вирішили якусь дугу взяти, то слід позначити досягнутими всі компоненти, в які входить ця дуга. Так, їх може бути багато (якщо дуга на зовнішньому рівні входить у вершину великої глибини), але кожна компонента виявиться досягнуто рівно один раз.

Це можна зробити легко, якщо заздалегідь для кожної компоненти зберегти посилання на зовнішню наступного рівня. Тоді, вирішивши взяти у відповідь якусь дугу, потрібно лише піднятися від однієї вершини в компоненти все більш високого рівня і помітити їх як відвідані. Рекомендую пронумерувати всі компоненти, які з'являються протягом роботи, цілими числами.

Дякую за увагу

Для тих, хто дочитав до кінця,подарунок у вигляді мого коду на цю тему.