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

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

Статья из группы Random
Часть 1 Часть 3 Часть 4 Базовые алгоритмы обхода графов Их два, по-русски их названия переводят как «поиск в глубину» и «поиск в ширину». Традиционные английские наименования чуть более точны: “Depth First Search” и “Breadth First Search”, то есть поиск с приоритетом глубины и ширины соответственно. Будем использовать аббревиатуры DFS и BFS. Назначение алгоритмов DFS и BFS – обнаружить и обойти все вершины связного графа. Способы достижения этого у них прямо противоположные: 1. DFS от стартового узла старается идти по ребрам вглубь графа, пока не застрянет в тупике, после чего возвращается к ближайшей развилке и опять идет максимально вглубь. Для отслеживания развилок используется стек. 2. BFS сначала обследует все смежные узлы. Для сохранения результатов используется очередь. Для решения нашей задачи нам потребуется модифицированный DFS, поэтому сосредоточимся на нем подробнее (здесь можно посмотреть прекрасно иллюстрированное объяснение алгоритма BFS). Возьмем граф посложнее: Немного о графах и словах - домино. Часть 2. - 1 Для того, чтобы не захламлять схему, мы не будем подписывать ребра, но можно самостоятельно убедиться, что граф представляет собой схему соединения по принципу домино данных английских слов (общим числом 21) . Стартовый узел в базовом DFS можно брать любой. Поехали! Нам потребуется стек для обеспечения возможности вернуться назад из возможного тупика (для backtracking’а). Отдельно заведем массив для результата работы алгоритма, каковым должен стать список из десяти узлов. Стартовым узлом назначим, скажем, S. Помечаем его как уже посещенный (желтым цветом) и, поскольку у него имеются ребра, указывающие на не посещенные пока (зеленые) узлы, заносим его в стек. Возможных ребер для дальнейшего движения два – (S, M) и (S, D). Выбираем наугад последнее (пометим это ребро синим на память) и «посещаем» узел D. Поскольку у него есть ребро, указывающее на «зеленый» узел, заносим его в стек. Немного о графах и словах - домино. Часть 2. - 2 «Посещаем» узел K, заносим его в стек. «Посещаем» узел L, заносим его в стек Немного о графах и словах - домино. Часть 2. - 3 Делаем то же самое с узлами A и E. Немного о графах и словах - домино. Часть 2. - 4 Узел E развилочный, в S мы идти не можем (он уже желтый), а вот N и T – зеленые. Кидаем жребий – и идем, например, в N. Потом идем в M. Немного о графах и словах - домино. Часть 2. - 5 И в узле B мы наконец упираемся в стенку. Казалось бы, тупик, но нет – время собирать урожай и заполнять массив результатов! Если у желтого узла не имеется ребер, ведущих в зеленые узлы, мы перемещаем его из стека в результат. Таким образом, из стека в результат на этом этапе выпрыгивают три узла: B, M и N. Немного о графах и словах - домино. Часть 2. - 6 Е имеет ребро в зеленый узел T, посещаем его, кладем в стек. Немного о графах и словах - домино. Часть 2. - 7 И сразу же вынимаем его оттуда, так как ни в какой зеленый узел из него попасть нельзя. То же самое будет относиться и ко всем оставшимся в стеке узлам. Стек опустошается. Нулевой размер стека – это сигнал к окончанию работы алгоритма DFS. Все десять узлов графа найдены. <-Назад Далее->
Комментарии
ЧТОБЫ ПОСМОТРЕТЬ ВСЕ КОММЕНТАРИИ ИЛИ ОСТАВИТЬ КОММЕНТАРИЙ,
ПЕРЕЙДИТЕ В ПОЛНУЮ ВЕРСИЮ