JavaRush /Java блог /Random /Немного о графах и словах - домино. Часть 1.
SergGlav
27 уровень
Москва

Немного о графах и словах - домино. Часть 1.

Статья из группы Random
Часть 2 Часть 3 Часть 4 Написать эту статью меня побудила вредная задача из квеста Java Multithreading, которая не без подколки со стороны разработчиков была названа ими «задачей на StringBuilder». Суть её условия состояла в том, что набор слов (в условии даны названия городов, что напоминает детскую игру «в слова») необходимо было расположить по принципу домино, последняя буква n’ного слова должна быть равной первой букве слова (n+1)го, причем было заведомо известно, что все данные (вразбивку) слова в такую цепочку складываются. Если можно было составить несколько вариантов искомой цепочки слов – в качестве решения принималась любая. При всей кажущейся простоте и наглядности условия, решить задачу было далеко не просто, и виртуозное владение StringBuilder'ом отнюдь не спасало ситуацию. Разработчиками задачи оказались упорядоченные изоморфы с планеты Линейный Хаос, которые не раз наводили ужас на курсантов JavaRush. Поверхностные решения ожидаемо не устраивали валидатор, так как обязательно находились такие цепочки, которые заставляли наивный алгоритм пропускать слова. Требовалось громоздить дополнительные «костыли», которые, усложняя задачу, не приближали решение в общем случае и всё более усиливали ощущение, что у простого условия должно быть не менее простое решение. Пришлось сменить тактику и немного погрузиться в более фундаментальные области. Сразу оговорюсь, что ни в коем случае не считаю себя специалистом в теории графов, темы, которые я затрону, почти не выходят за пределы решения задачи про слова-домино, за исключением, может быть, лишь пары отступлений теоретического характера. Итак, графы. Что такое граф: это коллекция (множество, набор, список – как угодно) вершин, соединенных между собой. Соединения принято называть ребрами (edges), вершины (vertices) еще называют узлами или нодами (nodes). Это граф: Немного о графах и словах - домино. Часть 1. - 1 Это тоже граф: Немного о графах и словах - домино. Часть 1. - 2 Если мы про ребро можем сказать, что оно имеет направление, то граф называется ориентированным: Немного о графах и словах - домино. Часть 1. - 3 Графы на первых двух рисунках – неориентированные. Про них можно сказать, что ребро (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. - 4 и соединим их словами Немного о графах и словах - домино. Часть 1. - 5 Как видим, у нас получился ориентированный граф, в котором узлы – это буквы, а ребра – это слова, их соединяющие. Если мы найдем способ пройти по всем ребрам от вершины к вершине так, чтобы посетить каждое ребро лишь единожды, наша задача будет решена. Попробуем распределить узлы на схеме немного иначе: Немного о графах и словах - домино. Часть 1. - 6 Теперь лучше видно, что наш граф представляет собой замкнутый цикл. Мы можем начать последовательность с любого слова, и это будет верным решением. Впрочем, условие задачи нам говорит о том, что достаточно будет одного любого решения. Заменим Вену на Владимир: Немного о графах и словах - домино. Часть 1. - 7 Мы видим два следствия: во-первых, нам пришлось добавить новую вершину, букву Р, а во-вторых, мы видим, что зациклить наш граф уже не получается. Суммируем всё вышеизложенное и введем два новых термина: 1. Связный граф, ребра которого можно обойти, посетив каждое лишь единожды, называется графом, содержащим «эйлеров путь». Признаком такого графа (кроме отсутствия вершин без ребер) является четная степень всех вершин, кроме двух (и только двух). 2. Если при этом оказывается возможным вернуться в исходный узел, мы говорим, что в графе существует «эйлеров цикл». Признаком такого графа (кроме отсутствия вершин без ребер) является четная степень всех вершин. Представим себе наш список городов так: {Москва Анапа Адлер Ростов-на-Дону Ухань}. Построим граф: Немного о графах и словах - домино. Часть 1. - 8 На схеме можно увидеть, что этот граф имеет эйлеров путь. Вершин с нечетной степенью только две – это М и Ь, остальные – чётные: А имеет степень 4, т.к. петля считается дважды, а Р и У имеют степень 2. Если мы придумаем алгоритм, который сможет на основе этой схемы построить эйлеров маршрут, скажем, в виде списка {М,А,А,Р,У,Ь} – то мы решим задачу, т.к. вывод слов в заданном порядке будет лишь делом техники. Таким образом, решение нашей задачи со словами-домино сводится к имплементации алгоритма по нахождению эйлерова пути (цикл при этом находится «бесплатно») в ориентированном графе. Далее ->
Комментарии (2)
ЧТОБЫ ПОСМОТРЕТЬ ВСЕ КОММЕНТАРИИ ИЛИ ОСТАВИТЬ КОММЕНТАРИЙ,
ПЕРЕЙДИТЕ В ПОЛНУЮ ВЕРСИЮ
Dregid Уровень 40
23 марта 2023
Искал медь - а нашел золото. Поняв что мне нужно изучить графы, наткнулся на эту статью. Отсюда тогда и начнем)
Benjam1nBTN Уровень 24
24 января 2023
Как же доходчиво! Класс!