Nicht rekursiver Tiefensuchalgorithmus

Ich suche nach einem nicht rekursiven Tiefensuchalgorithmus für einen nicht-binären Baum. Jede Hilfe wird sehr geschätzt.

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
}

Die Symmetrie der beiden ist ziemlich cool.

Update: Wie bereits erwähnt, take_first()wird das erste Element in der Liste entfernt und zurückgegeben.

Sie würden einen Stapel verwenden , der die Knoten enthält, die noch nicht besucht wurden:

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

Wenn Sie Zeiger auf übergeordnete Knoten haben, können Sie dies ohne zusätzlichen Speicher tun.

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

Beachten Sie, dass, wenn die untergeordneten Knoten als Array und nicht über Geschwisterzeiger gespeichert werden, das nächste Geschwister wie folgt gefunden werden kann:

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

Verwenden Sie einen Stapel, um Ihre Knoten zu verfolgen

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)

}

Während „einen Stapel verwenden“ könnte zu gekünstelt Interview - Frage als Antwort arbeiten, in Wirklichkeit tut es genau das, was explizit eine rekursive Programm den Kulissen tut hinter sich .

Die Rekursion verwendet den im Programm integrierten Stapel. Wenn Sie eine Funktion aufrufen, werden die Argumente für die Funktion auf den Stapel verschoben. Wenn die Funktion zurückgegeben wird, wird der Programmstapel geöffnet.

Eine ES6-Implementierung basierend auf biziclops gute Antwort:

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

                }
            }

Die allgemeine Logik besteht darin, einen Knoten (beginnend mit root) in den Wert Stack, Pop () it und Print () zu verschieben. Wenn dann Kinder (links und rechts) vorhanden sind, schieben Sie diese in den Stapel - drücken Sie zuerst Rechts, damit Sie zuerst das linke Kind besuchen (nachdem Sie den Knoten selbst besucht haben). Wenn der Stapel leer ist (), haben Sie alle Knoten in der Vorbestellung besucht.

Nicht rekursives DFS mit ES6-Generatoren

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

Es weicht von der typischen nicht rekursiven DFS ab, um leicht zu erkennen, wann alle erreichbaren Nachkommen eines bestimmten Knotens verarbeitet wurden, und um den aktuellen Pfad in der Liste / im Stapel beizubehalten.

Angenommen, Sie möchten eine Benachrichtigung ausführen, wenn jeder Knoten in einem Diagramm besucht wird. Die einfache rekursive Implementierung lautet:

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, jetzt möchten Sie eine stapelbasierte Implementierung, da Ihr Beispiel nicht funktioniert. Komplexe Diagramme können beispielsweise dazu führen, dass der Stapel Ihres Programms zerstört wird und Sie eine nicht rekursive Version implementieren müssen. Das größte Problem besteht darin, zu wissen, wann eine Benachrichtigung ausgegeben werden muss.

Der folgende Pseudocode funktioniert (Mischung aus Java und C ++ zur besseren Lesbarkeit):

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

Es sieht kompliziert aus, aber die zusätzliche Logik, die für die Ausgabe von Benachrichtigungen erforderlich ist, ist vorhanden, da Sie in umgekehrter Reihenfolge des Besuchs benachrichtigen müssen. DFS beginnt im Stammverzeichnis, benachrichtigt es jedoch zuletzt, im Gegensatz zu BFS, das sehr einfach zu implementieren ist.

Versuchen Sie für Kicks das folgende Diagramm: Die Knoten sind s, t, v und w. gerichtete Kanten sind: s-> t, s-> v, t-> w, v-> w und v-> t. Führen Sie Ihre eigene Implementierung von DFS aus, und die Reihenfolge, in der Knoten besucht werden sollen, muss lauten: w, t, v, s Eine umständliche Implementierung von DFS würde möglicherweise zuerst t benachrichtigen, was auf einen Fehler hinweist. Eine rekursive Implementierung von DFS würde immer w last erreichen.

VOLLES Beispiel ARBEITSCODE, ohne Stapel:

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

Ausgabe: Breite erste Durchquerung - ab Scheitelpunkt 2: 2 0 3 1 4 Tiefe erste Durchquerung - ab Scheitelpunkt 2: 2 3 4 1 0

Sie können einen Stapel verwenden. Ich habe Diagramme mit Adjacency Matrix implementiert:

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 iterativ in Java:

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

Habe gerade dieses Video gesehen und bin mit der Implementierung herausgekommen. Es sieht für mich leicht zu verstehen aus. Bitte kritisieren Sie dies.

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

Mit Stackden folgenden Schritten können Sie Folgendes ausführen: Schieben Sie dann den ersten Scheitelpunkt auf den Stapel.

1. Wenn möglich, besuchen Sie einen benachbarten nicht besuchten Scheitelpunkt, markieren Sie ihn und schieben Sie ihn auf den Stapel.
2. Wenn Sie Schritt 1 nicht ausführen können, entfernen Sie nach Möglichkeit einen Scheitelpunkt vom Stapel.
3. Wenn Sie Schritt 1 oder Schritt 2 nicht ausführen können, sind Sie fertig.

Hier ist das Java-Programm, das die obigen Schritte ausführt:

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

Pseudocode basierend auf der Antwort von @ biziclop:

• Verwenden Sie nur grundlegende Konstrukte: Variablen, Arrays, if, while und for
• Funktionen getNode(id)undgetChildren(id)
• Angenommene bekannte Anzahl von Knoten N

HINWEIS: Ich verwende die Array-Indizierung von 1, nicht von 0.

Breite zuerst

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

Tiefe zuerst

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

Hier ist ein Link zu einem Java - Programm zeigt DFS folgenden beiden reccursive und nicht-reccursive Methoden und auch die Berechnung Entdeckung und Finish Zeit, aber ohne Rand laleling.

    public void DFSIterative() {
    Reset();
    Stack<Vertex> s = new Stack<>();
    for (Vertex v : vertices.values()) {
        if (!v.visited) {
            v.d = ++time;
            v.visited = true;
            s.push(v);
            while (!s.isEmpty()) {
                Vertex u = s.peek();
                s.pop();
                boolean bFinished = true;
                for (Vertex w : u.adj) {
                    if (!w.visited) {
                        w.visited = true;
                        w.d = ++time;
                        w.p = u;
                        s.push(w);
                        bFinished = false;
                        break;
                    }
                }
                if (bFinished) {
                    u.f = ++time;
                    if (u.p != null)
                        s.push(u.p);
                }
            }
        }
    }
}

Vollständige Quelle hier .

Ich wollte nur meine Python-Implementierung zur langen Liste der Lösungen hinzufügen. Dieser nicht rekursive Algorithmus verfügt über Erkennungs- und Abschlussereignisse.

worklist = [root_node]
visited = set()
while worklist:
    node = worklist[-1]
    if node in visited:
        # Node is finished
        worklist.pop()
    else:
        # Node is discovered
        visited.add(node)
        for child in node.children:
            worklist.append(child)