Nierekurencyjny algorytm wyszukiwania głębi

Można użyć stos , który przechowuje węzły, które nie zostały jeszcze odwiedzone:

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

Jeśli masz wskaźniki do węzłów macierzystych, możesz to zrobić bez dodatkowej pamięci.

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

Zauważ, że jeśli węzły potomne są przechowywane jako tablica, a nie przez wskaźniki rodzeństwa, następne rodzeństwo można znaleźć jako:

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

Użyj stosu do śledzenia węzłów

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)

}

Podczas gdy "użyj stosu "może działać jako odpowiedź na wymyślone pytanie wywiadu, w rzeczywistości robi to wyraźnie, co program rekurencyjny robi za kulisami.

Rekurencja wykorzystuje programy wbudowane w stos. Gdy wywołujesz funkcję, wypycha ona argumenty do funkcji na stos, a gdy funkcja zwróci, robi to poprzez popping stos programu.

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);

                }
            }

Ogólna logika to: wcisnąć węzeł(zaczynając od roota) do stosu, Pop() go i print() wartość. Następnie jeśli ma dzieci( lewo i prawo) wciśnij je do stosu-wciśnij najpierw w prawo, aby najpierw odwiedzić lewe dziecko (po odwiedzeniu samego węzła). Gdy stos jest pusty (), odwiedzisz wszystkie węzły w przedsprzedaży.

Implementacja ES6 oparta na biziclops świetna odpowiedź:

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);
  }
}

Załóżmy, że chcesz wykonać powiadomienie, gdy każdy węzeł na wykresie jest odwiedzany. Prosta rekurencyjna implementacja to:

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
}

Ok, teraz chcesz implementację opartą na stosie, ponieważ twój przykład nie działa. Złożone wykresy mogą na przykład spowodować, że to zniszczy stos Twojego programu i będziesz musiał zaimplementować wersję Nie rekurencyjną. Największym problemem jest wiedzieć, kiedy wydać powiadomienie.

Następujący pseudo-kod działa (mieszanka Javy i C++ dla czytelność): {]}

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);
  }
}

Wygląda to na skomplikowane, ale dodatkowa logika potrzebna do wysyłania powiadomień istnieje, ponieważ musisz powiadamiać w odwrotnej kolejności wizyt - DFS zaczyna się od roota, ale powiadamia go jako ostatni, w przeciwieństwie do BFS, który jest bardzo prosty w implementacji.

Dla kopnięcia, spróbuj wykonać Wykres: Węzły To s, t, v i w. skierowane krawędzie są: s - > t, s - > v, t->w, v->w I v->t. Uruchom własną implementację DFS i kolejność odwiedzania węzłów musi być: w, t, v, s Niezdara implementacja DFS może najpierw powiadomić t, co wskazuje na błąd. Rekurencyjna implementacja DFS zawsze osiągnie w last.

Non-recursive DFS using ES6 generators

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 
  }    
}

Różni się odtypowych nie rekurencyjnych DFS , aby łatwo wykryć, kiedy wszystkie osiągalne potomkinie danego węzła zostały przetworzone i utrzymać bieżącą ścieżkę na liście/stosie.

Możesz użyć stosu. Zaimplementowałem wykresy z Macierzą Adjacencji:

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();
        }
    }
}

DFS iteracyjny w Javie:

//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

Właśnie obejrzałem ten filmik i wyszedł z implementacją. Łatwo mi to zrozumieć. Proszę, krytykuj to.

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()
}

Używając Stack, oto kroki, które należy wykonać: wciśnij pierwszy wierzchołek na stosie, a następnie

1. jeśli to możliwe, odwiedź sąsiadujący wierzchołek, zaznacz go, i wcisnąć go na stosie.
2. Jeśli nie możesz wykonać kroku 1, wtedy, jeśli to możliwe, usuń wierzchołek stack.
3. Jeśli nie możesz wykonać kroku 1 lub 2, jesteś skończony.

Oto program Java wykonujący powyższe kroki:

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);
            }
        }

Pseudo-kod na podstawie odpowiedzi @biziclop:

• używanie tylko podstawowych konstrukcji: zmiennych, tablic, if, while oraz for
• Funkcje getNode(id) i getChildren(id)
• zakładając znaną liczbę węzłów N

Uwaga: używam indeksowania tablic od 1, a nie 0.

Szerokość-pierwsza

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

Depth-first

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