Частина 2 Частина 3 Частина 4 Написати цю статтю мене спонукало шкідливе завдання з квесту Java Multithreading, яке не без підколки з боку розробників було названо ними «завданням на StringBuilder». Суть її умови полягала в тому, що набір слів (за умови дано назви міст, що нагадує дитячу гру «в слова») необхідно було розташувати за принципом доміно, остання буква n'ного слова повинна бути рівною першій букві слова (n+1) го, причому було свідомо відомо, що це дані (вразбивку) слова у такий ланцюжок складаються. Якщо можна було скласти кілька варіантів шуканого ланцюжка слів - як рішення приймалася будь-яка. При всій простоті і наочності умови, вирішити завдання було далеко не просто, і віртуозне володіння StringBuilder'ом аж ніяк не рятувало ситуацію. Розробниками завдання виявабося упорядковані ізоморфи з планети Лінійний Хаос, які неодноразово наводабо жах на курсантів JavaRush. Поверхневі рішення очікувано не влаштовували валідатор, тому що обов'язково знаходабося такі ланцюжки, які змушували наївний алгоритм пропускати слова. Потрібно нагромаджувати додаткові «мабоці», які, ускладнюючи завдання, не наближали рішення в загальному випадку і все більше посилювали відчуття, що у простої умови має бути не менш просте рішення. Довелося змінити тактику і трохи поринути у більш фундаментальні області. Відразу зазначу, що в жодному разі не вважаю себе фахівцем у теорії графів, теми, які я торкнуся, майже не виходять за межі вирішення завдання про слова-доміно, за винятком, можливо, лише пари відступів теоретичного характеру. Отже, графи. Що таке граф: це колекція (безліч, набір, список – як завгодно) вершин, з'єднаних між собою . З'єднання прийнято називати ребрами (edges), вершини (vertices) ще називають вузлами чи нодами (nodes). Це граф: Це теж граф: Якщо ми про ребро можемо сказати, що воно має напрямок, то граф називається орієнтованим : Графи на перших двох малюнках – неорієнтовані. Про них можна сказати, що ребро (u, v) ідентично ребру (v, u), тобто, наприклад, ребра (0, 4) і (4, 0) – це те саме ребро. Стрілки на ребрах орієнтованого графа означають, що ребро (u, v) – це шлях із вершини u у вершину v та ребро (v, u) немає. На третьому малюнку існує ребро (E, A). Ребра (A, E) немає. Подивимося на останній малюнок уважніше. Можна помітити, що вершина F немає ребер взагалі, таке цілком можливо. Також зауважимо, що біля вершини А з'явилося ребро – петля, а між вершинами B і D є два різноспрямовані ребра. Орієнтовані графи припускають такі артефакти. Допустимо, що граф описує групу знайомих, які дарують один одному подарунки. Ми бачимо, що жадібний F нічого нікому не подарував, B і D подарунками обмінялися (крім того, що кожен із них зробив по подарунку комусь ще), а A зробив подарунок самому собі, напевно, з нагоди успішного вирішення задачі з планети Лінійний Хаос. До речі, зауважимо, що вершини графа нічого не винні бути числами чи містити числа, це швидше контейнери, тобто. вони можуть зберігати будь-який об'єкт. Граф – це опис зв'язків. Важливий термін, який стане нам у нагоді – кількість ребер, прив'язаних до вершини (або, як ще кажуть, інцидентних їй) називається ступенем даної вершини. Наприклад, у першого малюнка вершина 0 має ступінь 2, 1 – ступінь 4, 3 – ступінь 3, вершина 0 другого малюнка має ступінь 1. Заглиблюватися в різноманіття різних типів графів ми в цій статті не будемо, тільки згадаємо, що існують ще зважені графи, тобто. такі, у яких до кожного ребра прив'язане деяке число, що означає ціну його проходження. У зв'язкових графів існує кілька підвидів, розрізняються за властивостями. Наприклад, графи, у яких ребра ніде не утворюють цикл, називаються деревами (у них є цікаві сімейства з приголомшливими назвами, такими як «червоно-чорні дерева», наприклад) і широко використовуються в різних важливих алгоритмах та структурах даних. Все це дуже цікаво, скажете ви, але яке відношення все це має до побудови ланцюжка слів? З'ясовується, що найпряміше. Подивимося на наш тестовий приклад з умови: {Амстердам Мельбурн Нью-Йорк Київ Відень}. Запишемо у будь-якому порядку «вузлові» літери, за які чіпляються слова: {А, М, Н, К, В} і з'єднаємо їх словами Як бачимо, у нас вийшов орієнтований граф, у якому вузли – це літери, а ребра – це слова , що їх з'єднують. Якщо ми знайдемо спосіб пройти по всіх ребрах від вершини до вершини так, щоб відвідати кожне ребро лише один раз, наше завдання буде вирішено. Спробуємо розподілити вузли на схемі трохи інакше: Тепер краще видно, що наш граф є замкнутим циклом. Ми можемо розпочати послідовність із будь-якого слова, і це буде вірним рішенням. Втім, умова завдання нам говорить про те, що достатньо одного будь-якого рішення. Замінимо Відень на Володимир: Ми бачимо два наслідки: по-перше, нам довелося додати нову вершину, літеру Р, а по-друге, бачимо, що зациклити наш граф уже не виходить. Підсумовуємо все вищевикладене і введемо два нових терміни: 1. Зв'язковий граф, ребра якого можна обійти, відвідавши кожне лише один раз, називається графом, що містить « ейлерів шлях» . Ознакою такого графа (крім відсутності вершин без ребер) є парний ступінь усіх вершин, крім двох (і лише двох). 2. Якщо у своїй виявляється можливим повернутися у вихідний вузол, говоримо, що у графі існує «ейлерів цикл» . Ознакою такого графа (крім відсутності вершин без ребер) є парний ступінь усіх вершин. Уявимо собі наш список міст так: Москва Анапа Адлер Ростов-на-Дону Ухань. Побудуємо граф: На схемі можна побачити, що цей граф має шлях ейлера. Вершин з непарною мірою лише дві – це М і Ь, інші – парні: А має ступінь 4, т.к. петля вважається двічі, а Р та У мають ступінь 2. Якщо ми придумаємо алгоритм, який зможе на основі цієї схеми побудувати ейлерів маршрут, скажімо, у вигляді списку {М,А,А,Р,У,Ь} – то ми вирішимо задачу , т.к. виведення слів у заданому порядку буде лише справою техніки. Таким чином, рішення нашого завдання зі словами-доміно зводиться до імплементації алгоритму знаходження ейлерового шляху (цикл при цьому знаходиться «безкоштовно») в орієнтованому графі. Далі ->
Це теж граф: 
Якщо ми про ребро можемо сказати, що воно має напрямок, то граф називається орієнтованим : 
Графи на перших двох малюнках – неорієнтовані. Про них можна сказати, що ребро (u, v) ідентично ребру (v, u), тобто, наприклад, ребра (0, 4) і (4, 0) – це те саме ребро. Стрілки на ребрах орієнтованого графа означають, що ребро (u, v) – це шлях із вершини u у вершину v та ребро (v, u) немає. На третьому малюнку існує ребро (E, A). Ребра (A, E) немає. Подивимося на останній малюнок уважніше. Можна помітити, що вершина F немає ребер взагалі, таке цілком можливо. Також зауважимо, що біля вершини А з'явилося ребро – петля, а між вершинами B і D є два різноспрямовані ребра. Орієнтовані графи припускають такі артефакти. Допустимо, що граф описує групу знайомих, які дарують один одному подарунки. Ми бачимо, що жадібний F нічого нікому не подарував, B і D подарунками обмінялися (крім того, що кожен із них зробив по подарунку комусь ще), а A зробив подарунок самому собі, напевно, з нагоди успішного вирішення задачі з планети Лінійний Хаос. До речі, зауважимо, що вершини графа нічого не винні бути числами чи містити числа, це швидше контейнери, тобто. вони можуть зберігати будь-який об'єкт. Граф – це опис зв'язків. Важливий термін, який стане нам у нагоді – кількість ребер, прив'язаних до вершини (або, як ще кажуть, інцидентних їй) називається ступенем даної вершини. Наприклад, у першого малюнка вершина 0 має ступінь 2, 1 – ступінь 4, 3 – ступінь 3, вершина 0 другого малюнка має ступінь 1. Заглиблюватися в різноманіття різних типів графів ми в цій статті не будемо, тільки згадаємо, що існують ще зважені графи, тобто. такі, у яких до кожного ребра прив'язане деяке число, що означає ціну його проходження. У зв'язкових графів існує кілька підвидів, розрізняються за властивостями. Наприклад, графи, у яких ребра ніде не утворюють цикл, називаються деревами (у них є цікаві сімейства з приголомшливими назвами, такими як «червоно-чорні дерева», наприклад) і широко використовуються в різних важливих алгоритмах та структурах даних. Все це дуже цікаво, скажете ви, але яке відношення все це має до побудови ланцюжка слів? З'ясовується, що найпряміше. Подивимося на наш тестовий приклад з умови: {Амстердам Мельбурн Нью-Йорк Київ Відень}. Запишемо у будь-якому порядку «вузлові» літери, за які чіпляються слова: {А, М, Н, К, В} 
і з'єднаємо їх словами 
Як бачимо, у нас вийшов орієнтований граф, у якому вузли – це літери, а ребра – це слова , що їх з'єднують. Якщо ми знайдемо спосіб пройти по всіх ребрах від вершини до вершини так, щоб відвідати кожне ребро лише один раз, наше завдання буде вирішено. Спробуємо розподілити вузли на схемі трохи інакше: 
Тепер краще видно, що наш граф є замкнутим циклом. Ми можемо розпочати послідовність із будь-якого слова, і це буде вірним рішенням. Втім, умова завдання нам говорить про те, що достатньо одного будь-якого рішення. Замінимо Відень на Володимир: 
Ми бачимо два наслідки: по-перше, нам довелося додати нову вершину, літеру Р, а по-друге, бачимо, що зациклити наш граф уже не виходить. Підсумовуємо все вищевикладене і введемо два нових терміни: 1. Зв'язковий граф, ребра якого можна обійти, відвідавши кожне лише один раз, називається графом, що містить « ейлерів шлях» . Ознакою такого графа (крім відсутності вершин без ребер) є парний ступінь усіх вершин, крім двох (і лише двох). 2. Якщо у своїй виявляється можливим повернутися у вихідний вузол, говоримо, що у графі існує «ейлерів цикл» . Ознакою такого графа (крім відсутності вершин без ребер) є парний ступінь усіх вершин. Уявимо собі наш список міст так: Москва Анапа Адлер Ростов-на-Дону Ухань. Побудуємо граф: 
На схемі можна побачити, що цей граф має шлях ейлера. Вершин з непарною мірою лише дві – це М і Ь, інші – парні: А має ступінь 4, т.к. петля вважається двічі, а Р та У мають ступінь 2. Якщо ми придумаємо алгоритм, який зможе на основі цієї схеми побудувати ейлерів маршрут, скажімо, у вигляді списку {М,А,А,Р,У,Ь} – то ми вирішимо задачу , т.к. виведення слів у заданому порядку буде лише справою техніки. Таким чином, рішення нашого завдання зі словами-доміно зводиться до імплементації алгоритму знаходження ейлерового шляху (цикл при цьому знаходиться «безкоштовно») в орієнтованому графі. Далі ->
ПЕРЕЙДІТЬ В ПОВНУ ВЕРСІЮ