Глубина Первый алгоритм от начальной точки

Question

Хорошо, я много огляделся по сети, и это просто не нажимает на меня.

У меня есть ArrayList towns = new ArrayList<Town> с городами, в которых я буду выполнять DFS.

я заполнить этот массив с ~ 8 городов

У меня есть целое число int i (индекс города в ArrayList, который имеет быть первым в пути)

У меня есть начальное расстояние double dist = 0

У меня есть функция distBetween(Town a, Town b), которая делает то, что она говорит.

У меня есть Arraylist route = new ArrayList<Town>(), который содержит порядок городов, в зависимости от пути, который я принимаю.

Теперь у меня есть основная функция (рекурсивная, согласно онлайн-исследованиям), которая выполняет поиск по глубине.

public static void dfs(){ 

    // what goes here 

} 

Мне нужно добавить города в массив маршрутов и удалить их в соответствии с алгоритмом поиска первой глубины. Мне также нужно изменить переменную dist.

Как бы я об этом узнал. Может ли кто-нибудь предоставить мне, может быть, какой-то псевдокод или комментарии, просто объясняющие, что делать. Я не могу использовать другие алгоритмы, которые я нашел в Интернете. Если бы я мог получить объяснение, характерное для моей ситуации, это было бы здорово.

Я могу удалить индекс i из town, если это облегчает процедуру поиска.

Answer 1

Я предполагаю, что у вас есть State класс со следующими атрибутами (если вы, как графики, использовать Node вместо State):

Set<Town> unused;  // towns not yet visited 
ArrayList<Town> path; // current path 
double dist;    // total distance in path 

Затем используйте код, подобный этому, чтобы рекурсивно попробовать каждый возможный путь с использованием DFS.При первом вызове используйте dfs(emptyState, startTown, null):

public static void dfs(State s, Town last, State best) { 
    s.path.add(last); 
    s.unused.remove(last); 
    if (unused.empty()) { 
     // all towns visited - distance and path are now complete 
     if (best == null || s.dist < best.dist) best = s; 
     return; 
    } 
    for (Town t : s.unused) { 
     State next = s.copy(); // a copy of State s 
     next.dist += distBetween(last, t); 
     dfs(next, t); 
    } 
} 

После вызова этой функции, все пути были посещены ровно один раз (в порядке ДФСА), и best будет содержать кратчайшие один. Остерегайтесь, для многих городов это становится очень медленным - O (n!).

Answer 2

ДФС Алгоритм

1. Входные вершины и ребра графа G = (V, E).
2. Введите исходную вершину и назначьте ее переменной S.
3. Направьте исходную вершину в стек.
4. Повторите шаги 5 и 6 до тех пор, пока стек не будет пустым.
5. Поместите верхний элемент стека и отобразите его.
6. Нажмите вершины, которые находятся рядом с только что высковленным элементом, если он не находится в очереди и не отображается (т.е. не посещается).
7. Выход.

Для хранения вершин и краев вам понадобится adjacency matrix.