Часть 1
Часть 2
Часть 3
ПРЕДУПРЕЖДЕНИЕ! Последняя часть статьи (неожиданно для меня разросшейся) будет содержать жесткие спойлеры для тех, кто еще не доделал задачу «Составить цепочку слов» из квеста Java Multithreading.
Итак, пример практической реализации алгоритма DFS, модифицированного под наши цели.
При написании примера я исходил из того, что входящие данные содержат последовательность слов, которые можно составить по принципу домино, и наш граф заведомо содержит эйлеров путь или цикл. Все проверки на валидность, таким образом, намеренно пропущены, вернее, в программе присутствует только один такого рода метод. Он определяет, имеется во входящей последовательности слов эйлеров цикл (то есть, можно ли её закольцевать), или же только эйлеров путь. Варианты, при которых входящая последовательность не приводится к эйлерову графу, не рассматриваются и не проверяются (читатель может это сделать в качестве упражнения).
Также отмечу, что при создании примеров я предпочитал удобочитаемость лаконизму.
****************************************
Для начала нам потребуется переменная, которая будет содержать наш граф. Будем хранить его в виде списка смежности, для этого создадим хешкарту, ключами которой будут буквы-«ноды», а значениями – списки исходящих из данной ноды ребер. Ребра, не мудрствуя особо, будем хранить просто в виде слов:
Map<String, List<String>> graph = new HashMap<>();
Заметим, что ноды (ключи) мы будем хранить как строки, содержащие одну букву в нижнем регистре, а не символы (исключительно дело вкуса).
Отдельно заведем список нод, исключительно ради удобства:
Set<String> nodes = new HashSet<>();
Для удобочитаемости кода напишем ещё два вспомогательных метода: firstLetterOf() и lastLetterOf():
String firstLetterOf(String word) {
return word.substring(0, 1).toLowerCase();
}
String lastLetterOf(String word) {
return word.substring(word.length() - 1).toLowerCase();
}
Эти два метода позволят нам (в том числе) не заботиться о регистре букв во входящей последовательности слов.
Вся программа будет состоять из одного класса, который мы назовем, к примеру, EulerPath. Граф и список нод будут полями класса, а проинициализируем мы их в конструкторе с параметром, который примет входящую последовательность слов:
import java.util.*;
class EulerPath {
Map<String, List<String>> graph = new HashMap<>(); // граф в виде списка смежности
Set<String> nodes = new HashSet<>(); // отдельный список нодов, для удобства
EulerPath(String[] inputSequence) { //конструктор
for (String word : inputSequence) {
nodes.add(firstLetterOf(word)); // создаем список нод
nodes.add(lastLetterOf(word));
}
for (String node : nodes) {
graph.put(node, new ArrayList<>()); // которым сразу инициализируем граф
}
for (String word : inputSequence) { // еще раз проходим по списку слов
String node = firstLetterOf(word); // поскольку ребро исходящее, то нода – это
List<String> tmp = graph.get(node);// первая буква. Берем список ребер
tmp.add(word); // и добавляем к нему текущее слово
}
}
String firstLetterOf(String word) {
return word.substring(0, 1).toLowerCase();
}
String lastLetterOf(String word) {
return word.substring(word.length() - 1).toLowerCase();
}
public static void main(String[] args) {
String[] inputSequence = {"Адлер", "Рыбинск", "Курган", "Нарьян-Мар", "Рим", "Мурманск", "Константинополь"};
EulerPath solution = new EulerPath(inputSequence); // создаем и инициализируем объект, содержащий граф
}
}
В методе main() мы создаем входящий список слов. Его можно было ввести с клавиатуры или из файла, но этот способ больше подходит для тестирования. Уже на этом этапе мы можем запустить программу и полюбоваться очень красивой мапой graph в дебаггере =)
Теперь напишем метод, который определит, с какой ноды мы начнем наш DFS-поиск. Мы уже знаем, что в случае эйлерова пути мы обязаны начать с первой ноды, а в случае цикла – можем начинать со случайно выбранной. Пойдем по наглядному пути: создадим хэшкарту нод, где значениями будут пары из двух чисел. Первое число будет количеством исходящих ребер, второе – входящих. Если числа в каждой паре будут одинаковыми (вспомним теорию – ноды с четными степенями) – у нас эйлеров цикл. В случае эйлерова пути в нашей хэшкарте будут две ноды с нечетной степенью, где количество входящих и исходящих будет отличаться на единицу. Та нода, в которой количество исходящих будет больше – это стартовая нода. Если количество нод с нечетными степенями больше двух или разница входящих и исходящих в них другая – граф не эйлеров, и этот факт мы сейчас не проверяем (читатель может это сделать позже в качестве упражнения). Пишем метод:
String getStartNode(String[] inputSequence) {
Map<String, Integer[]> counter = new HashMap<>(); // заводим хэшкарту
for (String node : nodes) { // ключи берем из списка нод
Integer[] tuplet = {0, 0}; // подготавливаем пару чисел
counter.put(node, tuplet); // инициализируем хэшкарту
}
for (String word : inputSequence) { // пробегаем по входящей последовательности
String fl = firstLetterOf(word); //берем первую букву
String ll = lastLetterOf(word); // и последнюю букву
Integer[] tmp = counter.get(fl); // берем текущее значение счетчика для первой буквы
tmp[0]++; // и инкрементируем его
tmp = counter.get(ll); // то же самое для второй буквы
tmp[1]++;
}
for (String node : counter.keySet()) {
if (counter.get(node)[0] > counter.get(node)[1]) { // смотрим, есть ли у нас нода, где
// количество исходящих соединений больше количества входящих
return node; // если есть, возвращаем её
}
}
return "any"; //если нет, возвращаем слово “any”
Можно запустить этот метод в методе main(), поставить точку останова и полюбоваться хэшкартой, которая анализирует наш граф!
Весь служебный аппарат создан, и теперь мы, наконец, пишем сам алгоритм решения задачи, модифицированный DFS, основной «мотор» нашего класса. Он четко следует плану, описанному в третьей части статьи:
1. В стек кладется стартовая нода, та, которую определил метод getStartNode(). Если он вернул слово “any”, то мы берем первый попавшийся элемент из сета nodes. Текущую ноду будем далее брать методом peek().
2. Создаем цикл while, который остановится, когда стек нод опустеет.
3. В цикле берем из текущей ноды список слов и, если он не пуст, перемещаем первое слово в стек ребер, а ноду, на которую указывает последняя буква слова – в стек нод. Теперь эта нода текущая.
4. Если список слов текущей ноды пуст – перемещаем ноду из стека в массив path, а слово – из списка ребер в массив result. Список ребер проверяем на isEmpty(), так как мы помним, что он опустошается на одну итерацию раньше.
Нам понадобятся четыре переменные:
List<String> result = new ArrayList<>(); // массив для результатов
List<String> path = new ArrayList<>(); // массив для хранения эйлерова пути (цикла)
Stack<String> vertexStack = new Stack<>(); // стек нод
Stack<String> edgeStack = new Stack<>(); // стек ребер (самих слов)
Сделаем их полями класса.
Сам метод займет менее двух десятков строк:
void findEulerPath(String startNode){
if(startNode.equals("any")) startNode = nodes.toArray(new String[0])[0];
vertexStack.push(startNode);
while (!vertexStack.isEmpty()){
List<string> currentEdgeList = graph.get(vertexStack.peek());
if(currentEdgeList.size() > 0){
edgeStack.push(currentEdgeList.get(0));
currentEdgeList.remove(0);
graph.put(vertexStack.peek(), currentEdgeList);
String currentNode = lastLetterOf(edgeStack.peek());
vertexStack.push(currentNode);
} else {
path.add(vertexStack.pop());
if(!edgeStack.isEmpty()) result.add(edgeStack.pop());
}
}
}
Собранная воедино программа доступна здесь.
<--Назад
ПЕРЕЙДИТЕ В ПОЛНУЮ ВЕРСИЮ