Algoritmo de primera búsqueda de profundidad no recursivo

173

Estoy buscando un algoritmo de primera búsqueda de profundidad no recursivo para un árbol no binario. Cualquier ayuda es muy apreciada.

pardusco
fuente
1
@Bart Kiers Un árbol en general, a juzgar por la etiqueta.
biziclop
13
La primera búsqueda en profundidad es un algoritmo recursivo. Las respuestas a continuación son nodos de exploración recursiva, simplemente no están usando la pila de llamadas del sistema para hacer su recursión, y en su lugar están usando una pila explícita.
Null Set
8
@ Conjunto nulo No, es solo un bucle. Por su definición, cada programa de computadora es recursivo. (Que, en cierto sentido de la palabra son.)
biziclop
1
@ Conjunto nulo: un árbol también es una estructura de datos recursiva.
Gumbo
2
@MuhammadUmer el principal beneficio de los enfoques iterativos sobre los recursivos cuando el iterativo se considera menos legible es que puede evitar el tamaño máximo de la pila / restricciones de profundidad de recursión que la mayoría de los sistemas / lenguajes de programación implementan para proteger la pila. Con una pila en memoria, su pila solo está limitada por la cantidad de memoria que su programa puede consumir, lo que generalmente permite una pila mucho más grande que el tamaño máximo de la pila de llamadas.
John B

Respuestas:

313

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
}

La simetría de los dos es bastante genial.

Actualización: como se señaló, take_first()elimina y devuelve el primer elemento de la lista.

biziclop
fuente
11
+1 por notar cuán similares son los dos cuando se hacen de forma no recursiva (como si fueran radicalmente diferentes cuando son recursivos, pero aún así ...)
corsiKa
3
Y luego, para agregar a la simetría, si utiliza una cola de prioridad mínima como margen, en su lugar, tiene un buscador de ruta más corto de una sola fuente.
Mark Peters
10
Por cierto, la .first()función también elimina el elemento de la lista. Como shift()en muchos idiomas. pop()también funciona y devuelve los nodos secundarios en orden de derecha a izquierda en lugar de izquierda a derecha.
Ariel
55
En mi opinión, el algo DFS es ligeramente incorrecto. Imagine 3 vértices todos conectados entre sí. El progreso debe ser: gray(1st)->gray(2nd)->gray(3rd)->blacken(3rd)->blacken(2nd)->blacken(1st). Pero su código produce: gray(1st)->gray(2nd)->gray(3rd)->blacken(2nd)->blacken(3rd)->blacken(1st).
Batman el
3
@learner Podría estar malinterpretando su ejemplo, pero si todos están conectados entre sí, eso no es realmente un árbol.
biziclop
40

Usaría una pila que contiene los nodos que aún no se visitaron:

stack.push(root)
while !stack.isEmpty() do
    node = stack.pop()
    for each node.childNodes do
        stack.push(stack)
    endfor
    // …
endwhile
Gumbo
fuente
2
@Gumbo Me pregunto si es un gráfico con ciclos. ¿Esto puede funcionar? Creo que puedo evitar agregar un nodo duplicado a la pila y puede funcionar. Lo que haré es marcar a todos los vecinos del nodo que aparecen y agregar un if (nodes are not marked)para juzgar si es apropiado ser empujado a la pila. ¿Eso puede funcionar?
Alston
1
@Stallman Podrías recordar los nodos que ya has visitado. Si solo visita nodos que aún no ha visitado, no realizará ningún ciclo.
Gumbo
@Gumbo ¿Qué quieres decir con doing cycles? Creo que solo quiero el orden de DFS. Es correcto o no, gracias.
Alston
Solo quería señalar que el uso de una pila (LIFO) significa la profundidad del primer recorrido. Si desea utilizar primero la amplitud, vaya con una cola (FIFO) en su lugar.
Según Lundberg
3
Vale la pena señalar que para tener un código equivalente como la respuesta más popular de @biziclop, debe empujar las notas secundarias en orden inverso ( for each node.childNodes.reverse() do stack.push(stack) endfor). Esto también es probablemente lo que quieres. Una buena explicación de por qué es así está en este video: youtube.com/watch?v=cZPXfl_tUkA endfor
Mariusz Pawelski
32

Si tiene punteros a los nodos principales, puede hacerlo sin memoria adicional.

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

Tenga en cuenta que si los nodos secundarios se almacenan como una matriz en lugar de a través de punteros hermanos, el siguiente hermano se puede encontrar como:

def next_sibling(node):
    try:
        i =    node.parent.child_nodes.index(node)
        return node.parent.child_nodes[i+1]
    except (IndexError, AttributeError):
        return None
aaz
fuente
Esta es una buena solución porque no utiliza memoria adicional o manipulación de una lista o pila (algunas buenas razones para evitar la recurrencia). Sin embargo, solo es posible si los nodos del árbol tienen enlaces a sus padres.
joeytwiddle
Gracias. Este algoritmo es genial. Pero en esta versión no puede eliminar la memoria del nodo en la función de visita. Este algoritmo puede convertir el árbol en una lista unida usando el puntero "first_child". Entonces puede recorrerlo y liberar la memoria del nodo sin recurrencia.
puchu
66
"Si tiene punteros a los nodos primarios, puede hacerlo sin memoria adicional": el almacenamiento del puntero a los nodos primarios usa algo de "memoria adicional" ...
rptr
1
@ rptr87 si no estaba claro, sin memoria adicional aparte de esos punteros.
Abhinav Gauniyal
Esto fallaría para árboles parciales donde el nodo no es la raíz absoluta, pero se puede solucionar fácilmente while not node.next_sibling or node is root:.
Basel Shishani,
5

Usa una pila para rastrear tus nodos

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)

}
corsiKa
fuente
1
@Dave O. No, porque hace retroceder a los hijos del nodo visitado frente a todo lo que ya está allí.
biziclop
Debo haber malinterpretado la semántica de push_back entonces.
Dave O.
@Dave tienes un muy buen punto. Estaba pensando que debería ser "empujar el resto de la cola" no "empujar hacia atrás". Lo editaré apropiadamente.
corsiKa
Si estás empujando hacia adelante, debería ser una pila.
vuelo
@Timmy, sí, no estoy seguro de lo que estaba pensando allí. @quasiverse Normalmente pensamos en una cola como una cola FIFO. Una pila se define como una cola LIFO.
corsiKa
4

Si bien "usar una pila" podría funcionar como la respuesta a la pregunta artificial de la entrevista, en realidad, simplemente está haciendo explícitamente lo que hace un programa recursivo detrás de escena.

La recursión utiliza la pila integrada de programas. Cuando llama a una función, inserta los argumentos de la función en la pila y cuando la función lo devuelve, abre la pila del programa.

Chris Bennet
fuente
77
Con la importante diferencia de que la pila de subprocesos está severamente limitada, y el algoritmo no recursivo usaría el montón mucho más escalable.
Yam Marcovic
1
Esta no es solo una situación artificial. He usado técnicas como esta en algunas ocasiones en C # y JavaScript para obtener ganancias de rendimiento significativas sobre los equivalentes de llamadas recursivas existentes. Es frecuente que la gestión de la recursividad con una pila en lugar de usar la pila de llamadas sea mucho más rápida y menos intensiva en recursos. Hay muchos gastos generales involucrados en colocar un contexto de llamada en una pila frente a que el programador pueda tomar decisiones prácticas sobre qué colocar en una pila personalizada.
Jason Jackson
4

Una implementación de ES6 basada en la excelente respuesta de biziclops:

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

Max Leizerovich
fuente
3
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);

                }
            }

La lógica general es, empujar un nodo (comenzando desde la raíz) en el valor Stack, Pop () it e Print (). Luego, si tiene hijos (izquierda y derecha), empújelos en la pila: empuje a la derecha primero para que visite al hijo izquierdo primero (después de visitar el nodo) Cuando la pila esté vacía (), habrá visitado todos los nodos en Pre-Order.

Sanj
fuente
2

DFS no recursivo con generadores ES6

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

Se desvía del típico DFS no recursivo para detectar fácilmente cuándo se procesaron todos los descendientes accesibles de un nodo dado y para mantener la ruta actual en la lista / pila.

Jarek Przygódzki
fuente
1

Suponga que desea ejecutar una notificación cuando se visita cada nodo en un gráfico. La implementación recursiva simple es:

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, ahora quieres una implementación basada en pila porque tu ejemplo no funciona. Los gráficos complejos pueden, por ejemplo, hacer que esto arruine la pila de su programa y usted necesita implementar una versión no recursiva. El mayor problema es saber cuándo emitir una notificación.

El siguiente pseudocódigo funciona (mezcla de Java y C ++ para facilitar la lectura):

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

Parece complicado, pero existe la lógica adicional necesaria para emitir notificaciones porque debe notificar en orden inverso de visita: DFS comienza en la raíz pero lo notifica al final, a diferencia de BFS, que es muy simple de implementar.

Para patadas, intente con el siguiente gráfico: los nodos son s, t, v y w. los bordes dirigidos son: s-> t, s-> v, t-> w, v-> w, y v-> t. Ejecute su propia implementación de DFS y el orden en que deben visitarse los nodos debe ser: w, t, v, s Una implementación torpe de DFS podría notificar a t primero y eso indica un error. Una implementación recursiva de DFS siempre llegaría al final.

usuario3804051
fuente
1

Ejemplo completo de código de trabajo, sin pila:

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

salida: primer recorrido transversal - a partir del vértice 2: 2 0 3 1 4 primer recorrido transversal - a partir del vértice 2: 2 3 4 1 0

Assaf Faybish
fuente
0

Puedes usar una pila. Implementé gráficos con la matriz de adyacencia:

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

DFS iterativo en 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;
}
Piyush Patel
fuente
La pregunta pide explícitamente un árbol no binario
user3743222
Necesita un mapa visitado para evitar el bucle infinito
spiralmoon
0

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

Acabo de ver este video y salió con la implementación. Me parece fácil de entender. Por favor critica esto.

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()
}
prog_guy
fuente
0

Utilizando Stack, estos son los pasos a seguir: empuje el primer vértice en la pila y luego,

  1. Si es posible, visite un vértice adyacente no visitado, márquelo y empújelo en la pila.
  2. Si no puede seguir el paso 1, entonces, si es posible, saque un vértice de la pila.
  3. Si no puede seguir el paso 1 o el paso 2, ya está.

Aquí está el programa Java siguiendo los pasos anteriores:

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;
}
Yogesh Umesh Vaity
fuente
0
        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);
            }
        }
iMobaio
fuente
0

Pseudocódigo basado en la respuesta de @ biziclop:

  • Usando solo construcciones básicas: variables, matrices, if, while y for
  • Funciones getNode(id)ygetChildren(id)
  • Asumiendo un número conocido de nodos N

NOTA: Uso indexación de matriz desde 1, no desde 0.

Primero ancho

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

Profundidad primero

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
Jonathan H
fuente
0

Aquí hay un enlace a un programa java que muestra DFS siguiendo métodos recursivos y no recursivos y también calculando el tiempo de descubrimiento y finalización , pero sin laleling de bordes.

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

Fuente completa aquí .

Suhasis
fuente
0

Solo quería agregar mi implementación de Python a la larga lista de soluciones. Este algoritmo no recursivo tiene eventos de descubrimiento y finalizados.


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)
Windel
fuente