algorithm - grafos - busqueda por profundidad en java

Algoritmo de primera búsqueda de profundidad no recursiva

Question

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

Answer 1

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

Answer 2

DFS no recursivo usando 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 alcanzables de un nodo determinado y para mantener la ruta actual en la lista / pila.

Answer 3

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 buena.

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

Answer 4

Puedes usar una pila. Implementé gráficos con 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();
        }
    }
}

Answer 5

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

Recursion usa la pila integrada de programas. Cuando llama a una función, empuja los argumentos a la función en la pila y cuando la función regresa lo hace al abrir la pila de programas.

Answer 6

Si tiene punteros a 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

Answer 7

Supongamos que desea ejecutar una notificación cuando se visita cada nodo en un gráfico. La simple implementación recursiva 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 debe implementar una versión no recursiva. El mayor problema es saber cuándo emitir una notificación.

El siguiente pseudo-código funciona (mezcla de Java y C ++ para la legibilidad):

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 la lógica adicional necesaria para emitir notificaciones existe porque necesita notificar en el orden inverso de la visita: DFS se inicia en la raíz pero se lo notifica por última vez, a diferencia de BFS, que es muy fácil de implementar.

Para las patadas, intente seguir el 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 se deben visitar los nodos debe ser: w, t, v, s Una implementación torpe del DFS podría notificar t primero y eso indica un error. Una implementación recursiva de DFS siempre llegaría a w last.

Answer 8

Una implementación de ES6 basada en la gran 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);
  }
}

Answer 9

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)

}

Answer 10

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

1. Si es posible, visite un vértice no visitado adyacente, márquelo e introdúzcalo 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, ha terminado.

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

Answer 11

Utilizarías una stack que contiene los nodos que aún no se han visitado:

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

Answer 12

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

Answer 13

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

Answer 14

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, insertar un nodo (comenzando desde la raíz) en el valor Pila, Pop () e Imprimir (). Luego, si tiene hijos (izquierda y derecha), empújelos a la pila: pulse Derecha primero para que vaya primero a la izquierda (después de visitar el nodo). Cuando la pila está vacía (), habrá visitado todos los nodos en Pre-Order.