Реализация глубины Первый поиск в Java

Question

У меня есть домашняя работа, где мне нужно реализовать DFS в java. это псевдокод было дано задание 1.

DFS(V,E,s) 

foreach u ∈ V 
    vis(u) <-- 0 
    p[u] <-- NULL 

DFS-Visit(u) 
    vis(u) <-- 1 

work through u here foreach neighbor v to u 
if vis(u) = 0 
    p[v] = u 
DFS-Visit(v) 

И до сих пор это то, что я получил:

package kth.id2010.lab.lab05; 

public class DFS { 
    private static boolean[] visited; 
    private static int[] path; 

    static void DFS(int vertecies[], int edges[], int sourceVertex){ 

     for(int i = 0; i < vertecies.length; i++){ 
      visited[i] = false; 
      dfsVisit(i); 
     } 

    } 
    static void dfsVisit(int u){ 
     visited[u] = true; 
    } 
} 

Так что, если я думал corectly я добрался до той части, где мне нужно работать через u для соседнего v в u. И я не уверен, как это сделать.

Answer 1

Хорошо, если это просто итерация соседей, то здесь это место, чтобы начать:

DFS означает, что вы хотите, чтобы развернуть узел весь путь, прежде чем перейти ко второму соседу так, как вы, вероятно, учили , это первый в прошлом подход. С практической точки зрения вы можете начать с пустого объекта Stack и добавить к нему первый узел, используя Stack.push(). Затем вы можете сделать while !Stack.empty(): Stack.pop(). Это приведет к удалению последнего вставленного элемента. Затем вы повторяете каждый элемент рекурсивно (вызываете этот метод в цикле for) и повторяете до тех пор, пока не закончите соседей, после чего ничего не вернете.

Вопрос в том, каковы эти «элементы»? Если вы нажимаете массивы [start,end], то когда вы его поп, какие соседи вам нужны, чтобы вернуться к рекурсии? Хорошо, если вы подумаете об этом немного, вы поймете, что соседи узла с этим представлением будут все узлы, чья точка родительского узла end соответствует точке start любого другого узла (который не был посещен).

Наивный способ реализации, что является хорошим способом для начала, будет следующее (псевдокод):

while (!Stack.empty()): 
    current_node = Stack.pop(); 
    foreach node in all_nodes: 
     if current_node[1] == node[0] and node.not_visited_yet(): Stack.push(node) 
    // now we have the neighbors for this current_node pushed into the Stack 
    // Note that node.not_visited_yet() could be a function that keeps track of nodes 
    // that you already visited somehow (a map from node to boolean perhaps?) 

Это на самом деле это так далеко, как обходе свое дерево. Конечно, все это - это траверс, это не делает ничего значимого, но это не ваш вопрос. Если вы хотите, например, вернуть строку при достижении определенного узла, просто добавьте ее ниже цикла for. Вы также можете сделать это функцией, которая принимает в узле и стеке, а не использовать цикл while, а скорее вернется, как только вы достигнете конечной цели.

function DFS (Stack, current_node): // recursive 
    current_node = Stack.pop(); 
    foreach node in all_nodes: 
     if current_node[1] == node[0] and node.not_visited_yet(): Stack.push(node) 
    if not Stack.empty: 
     next_node = Stack.pop() 
     return DFS(Stack, next_node)