비 재귀 깊이 우선 검색 알고리즘

비 재귀 깊이 우선 검색 알고리즘

---

이진이 아닌 트리에 대한 비 재귀 깊이 우선 검색 알고리즘을 찾고 있습니다. 어떤 도움이라도 대단히 감사합니다.

---

DFS :

list nodes_to_visit = {root};
while( nodes_to_visit isn't empty ) {
  currentnode = nodes_to_visit.take_first();
  nodes_to_visit.prepend( currentnode.children );
  //do something
}

BFS :

list nodes_to_visit = {root};
while( nodes_to_visit isn't empty ) {
  currentnode = nodes_to_visit.take_first();
  nodes_to_visit.append( currentnode.children );
  //do something
}

이 둘의 대칭은 매우 멋집니다.

업데이트 : 지적했듯이 take_first()목록의 첫 번째 요소를 제거하고 반환합니다.

---

아직 방문하지 않은 노드를 보유 하는 스택 을 사용합니다 .

stack.push(root)
while !stack.isEmpty() do
    node = stack.pop()
    for each node.childNodes do
        stack.push(stack)
    endfor
    // …
endwhile

---

부모 노드에 대한 포인터가 있으면 추가 메모리없이 할 수 있습니다.

def dfs(root):
    node = root
    while True:
        visit(node)
        if node.first_child:
            node = node.first_child      # walk down
        else:
            while not node.next_sibling:
                if node is root:
                    return
                node = node.parent       # walk up ...
            node = node.next_sibling     # ... and right

자식 노드가 형제 포인터를 통하지 않고 배열로 저장된 경우 다음 형제를 다음과 같이 찾을 수 있습니다.

def next_sibling(node):
    try:
        i =    node.parent.child_nodes.index(node)
        return node.parent.child_nodes[i+1]
    except (IndexError, AttributeError):
        return None

---

스택을 사용하여 노드 추적

Stack<Node> s;

s.prepend(tree.head);

while(!s.empty) {
    Node n = s.poll_front // gets first node

    // do something with q?

    for each child of n: s.prepend(child)

}

---

biziclops에 대한 ES6 구현은 훌륭한 답변입니다.

root = {
  text: "root",
  children: [{
    text: "c1",
    children: [{
      text: "c11"
    }, {
      text: "c12"
    }]
  }, {
    text: "c2",
    children: [{
      text: "c21"
    }, {
      text: "c22"
    }]
  }, ]
}

console.log("DFS:")
DFS(root, node => node.children, node => console.log(node.text));

console.log("BFS:")
BFS(root, node => node.children, node => console.log(node.text));

function BFS(root, getChildren, visit) {
  let nodesToVisit = [root];
  while (nodesToVisit.length > 0) {
    const currentNode = nodesToVisit.shift();
    nodesToVisit = [
      ...nodesToVisit,
      ...(getChildren(currentNode) || []),
    ];
    visit(currentNode);
  }
}

function DFS(root, getChildren, visit) {
  let nodesToVisit = [root];
  while (nodesToVisit.length > 0) {
    const currentNode = nodesToVisit.shift();
    nodesToVisit = [
      ...(getChildren(currentNode) || []),
      ...nodesToVisit,
    ];
    visit(currentNode);
  }
}

---

"스택 사용" 은 면담 질문에 대한 해답으로 작용할 수 있지만 실제로 재귀 프로그램이 배후에서하는 일을 명시 적으로 수행하는 것입니다.

재귀는 프로그램 내장 스택을 사용합니다. 함수를 호출하면 함수의 인수를 스택으로 푸시하고 함수가 반환되면 프로그램 스택을 팝핑하여 반환합니다.

---

PreOrderTraversal is same as DFS in binary tree. You can do the same recursion 
taking care of Stack as below.

    public void IterativePreOrder(Tree root)
            {
                if (root == null)
                    return;
                Stack s<Tree> = new Stack<Tree>();
                s.Push(root);
                while (s.Count != 0)
                {
                    Tree b = s.Pop();
                    Console.Write(b.Data + " ");
                    if (b.Right != null)
                        s.Push(b.Right);
                    if (b.Left != null)
                        s.Push(b.Left);

                }
            }

일반적인 논리는 루트에서 시작하여 노드를 스택에 넣고 Pop () 및 Print () 값을 푸시하는 것입니다. 그런 다음 자식이있는 경우 (왼쪽 및 오른쪽) 스택에 밀어 넣으십시오-먼저 오른쪽을 눌러 왼쪽 자식을 먼저 방문하십시오 (노드 자체를 방문한 후). stack이 비면 () 주문 전의 모든 노드를 방문했을 것입니다.

---

ES6 생성기를 사용하는 비 재귀 DFS

class Node {
  constructor(name, childNodes) {
    this.name = name;
    this.childNodes = childNodes;
    this.visited = false;
  }
}

function *dfs(s) {
  let stack = [];
  stack.push(s);
  stackLoop: while (stack.length) {
    let u = stack[stack.length - 1]; // peek
    if (!u.visited) {
      u.visited = true; // grey - visited
      yield u;
    }

    for (let v of u.childNodes) {
      if (!v.visited) {
        stack.push(v);
        continue stackLoop;
      }
    }

    stack.pop(); // black - all reachable descendants were processed 
  }    
}

특정 비재 귀적 DFS 에서 벗어나 특정 노드의 도달 가능한 모든 하위 항목이 언제 처리되었는지 쉽게 감지하고 목록 / 스택에서 현재 경로를 유지합니다.

---

그래프의 각 노드를 방문 할 때 알림을 실행한다고 가정합니다. 간단한 재귀 구현은 다음과 같습니다.

void DFSRecursive(Node n, Set<Node> visited) {
  visited.add(n);
  for (Node x : neighbors_of(n)) {  // iterate over all neighbors
    if (!visited.contains(x)) {
      DFSRecursive(x, visited);
    }
  }
  OnVisit(n);  // callback to say node is finally visited, after all its non-visited neighbors
}

자, 이제 예제가 작동하지 않기 때문에 스택 기반 구현을 원합니다. 예를 들어 복잡한 그래프로 인해 프로그램 스택이 손상 될 수 있으며 비 재귀 버전을 구현해야합니다. 가장 큰 문제는 알림을 언제 발행해야 하는지를 아는 것입니다.

다음 의사 코드 작동 (가독성을 위해 Java와 C ++의 혼합) :

void DFS(Node root) {
  Set<Node> visited;
  Set<Node> toNotify;  // nodes we want to notify

  Stack<Node> stack;
  stack.add(root);
  toNotify.add(root);  // we won't pop nodes from this until DFS is done
  while (!stack.empty()) {
    Node current = stack.pop();
    visited.add(current);
    for (Node x : neighbors_of(current)) {
      if (!visited.contains(x)) {
        stack.add(x);
        toNotify.add(x);
      }
    }
  }
  // Now issue notifications. toNotifyStack might contain duplicates (will never
  // happen in a tree but easily happens in a graph)
  Set<Node> notified;
  while (!toNotify.empty()) {
  Node n = toNotify.pop();
  if (!toNotify.contains(n)) {
    OnVisit(n);  // issue callback
    toNotify.add(n);
  }
}

복잡해 보이지만 방문 순서를 반대로 통지해야하기 때문에 알림을 발행하는 데 필요한 추가 논리가 존재합니다. DFS는 루트에서 시작하지만 구현이 매우 간단한 BFS와 달리 마지막에 알립니다.

차기의 경우 노드는 s, t, v 및 w입니다. 지정된 모서리는 s-> t, s-> v, t-> w, v-> w 및 v-> t입니다. DFS의 자체 구현을 실행하고 방문해야하는 순서는 다음과 같아야합니다. w, t, v, s DFS의 서투른 구현은 t를 먼저 알리고 버그를 나타냅니다. DFS의 재귀 구현은 항상 마지막에 도달합니다.

---

스택이없는 전체 예제 작업 코드 :

import java.util.*;

class Graph {
private List<List<Integer>> adj;

Graph(int numOfVertices) {
    this.adj = new ArrayList<>();
    for (int i = 0; i < numOfVertices; ++i)
        adj.add(i, new ArrayList<>());
}

void addEdge(int v, int w) {
    adj.get(v).add(w); // Add w to v's list.
}

void DFS(int v) {
    int nodesToVisitIndex = 0;
    List<Integer> nodesToVisit = new ArrayList<>();
    nodesToVisit.add(v);
    while (nodesToVisitIndex < nodesToVisit.size()) {
        Integer nextChild= nodesToVisit.get(nodesToVisitIndex++);// get the node and mark it as visited node by inc the index over the element.
        for (Integer s : adj.get(nextChild)) {
            if (!nodesToVisit.contains(s)) {
                nodesToVisit.add(nodesToVisitIndex, s);// add the node to the HEAD of the unvisited nodes list.
            }
        }
        System.out.println(nextChild);
    }
}

void BFS(int v) {
    int nodesToVisitIndex = 0;
    List<Integer> nodesToVisit = new ArrayList<>();
    nodesToVisit.add(v);
    while (nodesToVisitIndex < nodesToVisit.size()) {
        Integer nextChild= nodesToVisit.get(nodesToVisitIndex++);// get the node and mark it as visited node by inc the index over the element.
        for (Integer s : adj.get(nextChild)) {
            if (!nodesToVisit.contains(s)) {
                nodesToVisit.add(s);// add the node to the END of the unvisited node list.
            }
        }
        System.out.println(nextChild);
    }
}

public static void main(String args[]) {
    Graph g = new Graph(5);

    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 2);
    g.addEdge(2, 0);
    g.addEdge(2, 3);
    g.addEdge(3, 3);
    g.addEdge(3, 1);
    g.addEdge(3, 4);

    System.out.println("Breadth First Traversal- starting from vertex 2:");
    g.BFS(2);
    System.out.println("Depth First Traversal- starting from vertex 2:");
    g.DFS(2);
}}

출력 : 정점에서 시작하는 폭 1 차 순회 : 2 0 3 1 4 정점에서 시작하는 폭 1 차 순회 : 2 3 4 1 0

---

스택을 사용할 수 있습니다. Adjacency Matrix를 사용하여 그래프를 구현했습니다.

void DFS(int current){
    for(int i=1; i<N; i++) visit_table[i]=false;
    myStack.push(current);
    cout << current << "  ";
    while(!myStack.empty()){
        current = myStack.top();
        for(int i=0; i<N; i++){
            if(AdjMatrix[current][i] == 1){
                if(visit_table[i] == false){ 
                    myStack.push(i);
                    visit_table[i] = true;
                    cout << i << "  ";
                }
                break;
            }
            else if(!myStack.empty())
                myStack.pop();
        }
    }
}

---

Java에서 DFS 반복 :

//DFS: Iterative
private Boolean DFSIterative(Node root, int target) {
    if (root == null)
        return false;
    Stack<Node> _stack = new Stack<Node>();
    _stack.push(root);
    while (_stack.size() > 0) {
        Node temp = _stack.peek();
        if (temp.data == target)
            return true;
        if (temp.left != null)
            _stack.push(temp.left);
        else if (temp.right != null)
            _stack.push(temp.right);
        else
            _stack.pop();
    }
    return false;
}

---

http://www.youtube.com/watch?v=zLZhSSXAwxI

방금이 비디오를보고 구현했습니다. 이해하기 쉬워 보입니다. 이것을 비판하십시오.

visited_node={root}
stack.push(root)
while(!stack.empty){
  unvisited_node = get_unvisited_adj_nodes(stack.top());
  If (unvisited_node!=null){
     stack.push(unvisited_node);  
     visited_node+=unvisited_node;
  }
  else
     stack.pop()
}

---

를 사용 Stack하여 수행 할 단계는 다음과 같습니다. 스택의 첫 번째 정점을 누른 다음,

1. 가능하면 방문하지 않은 인접한 정점을 방문하여 표시 한 다음 스택에 밀어 넣으십시오.
2. 1 단계를 수행 할 수 없으면 가능한 경우 스택에서 정점을 팝하십시오.
3. 1 단계 또는 2 단계를 수행 할 수 없으면 완료된 것입니다.

---

위의 단계를 따르는 Java 프로그램은 다음과 같습니다.

public void searchDepthFirst() {
    // begin at vertex 0
    vertexList[0].wasVisited = true;
    displayVertex(0);
    stack.push(0);
    while (!stack.isEmpty()) {
        int adjacentVertex = getAdjacentUnvisitedVertex(stack.peek());
        // if no such vertex
        if (adjacentVertex == -1) {
            stack.pop();
        } else {
            vertexList[adjacentVertex].wasVisited = true;
            // Do something
            stack.push(adjacentVertex);
        }
    }
    // stack is empty, so we're done, reset flags
    for (int j = 0; j < nVerts; j++)
            vertexList[j].wasVisited = false;
}

---

        Stack<Node> stack = new Stack<>();
        stack.add(root);
        while (!stack.isEmpty()) {
            Node node = stack.pop();
            System.out.print(node.getData() + " ");

            Node right = node.getRight();
            if (right != null) {
                stack.push(right);
            }

            Node left = node.getLeft();
            if (left != null) {
                stack.push(left);
            }
        }

---

@biziclop의 답변을 기반으로 한 의사 코드 :

• 변수, 배열, if, while 및 for와 같은 기본 구문 만 사용
• 기능 getNode(id)및getChildren(id)
• 알려진 수의 노드를 가정 N

---

참고 : 0이 아닌 1의 배열 색인을 사용합니다.

너비 우선

S = Array(N)
S[1] = 1; // root id
cur = 1;
last = 1
while cur <= last
    id = S[cur]
    node = getNode(id)
    children = getChildren(id)

    n = length(children)
    for i = 1..n
        S[ last+i ] = children[i]
    end
    last = last+n
    cur = cur+1

    visit(node)
end

깊이 우선

S = Array(N)
S[1] = 1; // root id
cur = 1;
while cur > 0
    id = S[cur]
    node = getNode(id)
    children = getChildren(id)

    n = length(children)
    for i = 1..n
        // assuming children are given left-to-right
        S[ cur+i-1 ] = children[ n-i+1 ] 

        // otherwise
        // S[ cur+i-1 ] = children[i] 
    end
    cur = cur+n-1

    visit(node)
end

참고URL : https://stackoverflow.com/questions/5278580/non-recursive-depth-first-search-algorithm