깊이 우선 Java 검색 구현

Question

자바에서 DFS를 구현해야하는 숙제가 있습니다. 이 의사는 작업 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에 foreach 이웃 v. 그리고 어떻게해야할지 모르겠다.

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)