Algoritmo de primeira pesquisa de profundidade não recursiva

173

Eu estou procurando um algoritmo de pesquisa de profundidade não recursiva em primeiro lugar para uma árvore não binária. Qualquer ajuda é muito apreciada.

mousey
fonte
1
@Bart Kiers Uma árvore em geral, a julgar pela etiqueta.
biziclop
13
A primeira pesquisa de profundidade é um algoritmo recursivo. As respostas abaixo estão explorando recursivamente os nós, eles simplesmente não estão usando a pilha de chamadas do sistema para fazer sua recursão e estão usando uma pilha explícita.
Null Set
8
@ Null Set Não, é apenas um loop. Por sua definição, todo programa de computador é recursivo. (O que, em certo sentido da palavra que eles são.)
biziclop
1
@Null Set: Uma árvore também é uma estrutura de dados recursiva.
Gumbo
2
O principal benefício do iterativo sobre as abordagens recursivas quando a iterativa é considerada menos legível é que você pode evitar restrições máximas de tamanho / profundidade de recursão da pilha que a maioria dos sistemas / linguagens de programação implementa para proteger a pilha. Com uma pilha de memória, sua pilha é limitada apenas pela quantidade de memória que seu programa pode consumir, o que normalmente permite uma pilha muito maior que o tamanho máximo da pilha de chamadas.
19418 John B

Respostas:

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
}

A simetria dos dois é bem legal.

Atualização: como indicado, take_first()remove e retorna o primeiro elemento da lista.

Biziclop
fonte
11
+1 para notar o quão semelhantes os dois são quando feito não-recursivamente (como se eles são radicalmente diferentes quando estão recursiva, mas ainda assim ...)
corsiKa
3
E, para adicionar à simetria, se você usar uma fila de prioridade mínima como franja, terá um localizador de caminho mais curto de fonte única.
Mark Peters
10
BTW, a .first()função também remove o elemento da lista. Como shift()em muitas línguas. pop()também funciona e retorna os nós filhos na ordem da direita para a esquerda, em vez de da esquerda para a direita.
Ariel
5
IMO, o algo DFS está um pouco incorreto. Imagine 3 vértices todos conectados um ao outro. O progresso deve ser: gray(1st)->gray(2nd)->gray(3rd)->blacken(3rd)->blacken(2nd)->blacken(1st). Mas seu código produz: gray(1st)->gray(2nd)->gray(3rd)->blacken(2nd)->blacken(3rd)->blacken(1st).
batman
3
@learner Eu posso estar entendendo mal o seu exemplo, mas se eles estão todos conectados, isso não é realmente uma árvore.
biziclop
40

Você usaria uma pilha que contém os nós que ainda não foram visitados:

stack.push(root)
while !stack.isEmpty() do
    node = stack.pop()
    for each node.childNodes do
        stack.push(stack)
    endfor
    // …
endwhile
quiabo
fonte
2
@ Gumbo Gostaria de saber se é um gráfico com cycyles. Isso pode funcionar? Eu acho que posso evitar adicionar um nó duplicado à pilha e ele pode funcionar. O que farei é marcar todos os vizinhos do nó que aparecerem e adicionar um if (nodes are not marked)para julgar se é apropriado ser empurrado para a pilha. Isso pode funcionar?
Alston
1
@Stallman Você pode se lembrar dos nós que você já visitou. Se você visitar apenas os nós que ainda não visitou, não fará nenhum ciclo.
Gumbo #
@Gumbo Como assim doing cycles? Eu acho que só quero a ordem do DFS. Está certo ou não, obrigado.
Alston
Só queria ressaltar que o uso de uma pilha (LIFO) significa a profundidade da primeira travessia. Se você deseja usar a largura em primeiro lugar, vá com uma fila (FIFO).
Per Lundberg
3
Vale a pena notar que, para ter um código equivalente como a resposta mais popular do @biziclop, é necessário enviar anotações filho na ordem inversa ( for each node.childNodes.reverse() do stack.push(stack) endfor). Provavelmente também é isso que você deseja. Boa explicação por que é assim é neste vídeo: youtube.com/watch?v=cZPXfl_tUkA endfor
Mariusz Pawelski
32

Se você tiver ponteiros para nós pai, poderá fazê-lo sem memória 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

Observe que, se os nós filhos forem armazenados como uma matriz, e não através de ponteiros para irmãos, o próximo irmão poderá ser encontrado 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
fonte
Essa é uma boa solução, pois não utiliza memória ou manipulação adicional de uma lista ou pilha (algumas boas razões para evitar recursões). No entanto, isso só é possível se os nós da árvore tiverem links para seus pais.
Joeytwiddle
Obrigado. Esse algoritmo é ótimo. Mas nesta versão você não pode excluir a memória do nó na função de visita. Esse algoritmo pode converter a árvore em lista vinculada única usando o ponteiro "first_child". Você pode percorrê-lo e liberar a memória do nó sem recursão.
puchu
6
"Se você tem ponteiros para nós pai, você pode fazê-lo sem memória adicional": armazenar ponteiro para nós pai faz usar alguns "memória adicional" ...
rptr
1
@ rptr87 se não estiver claro, sem memória adicional além desses indicadores.
Abhinav Gauniyal 6/11
Isso falharia em árvores parciais em que o nó não é a raiz absoluta, mas pode ser facilmente corrigido por while not node.next_sibling or node is root:.
Basel Shishani
5

Use uma pilha para rastrear seus nós

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
fonte
1
@ Dave O. Não, porque você empurra os filhos do nó visitado na frente de tudo o que já está lá.
biziclop
Devo ter interpretado mal a semântica de push_back então.
Dave O.
@ Dave você tem um ponto muito bom. Eu estava pensando que deveria estar "empurrando o resto da fila de volta" e não "empurrando para trás". Vou editar adequadamente.
corsiKa
Se você está empurrando para a frente, deve ser uma pilha.
vôo
@ Timmy sim, eu não tenho certeza do que estava pensando lá. @ quasiverse Normalmente pensamos em uma fila como uma fila FIFO. Uma pilha é definida como uma fila LIFO.
corsiKa
4

Enquanto "usar uma pilha" pode funcionar como a resposta para uma pergunta artificial da entrevista, na realidade, é apenas fazer explicitamente o que um programa recursivo faz nos bastidores.

A recursão usa a pilha incorporada dos programas. Quando você chama uma função, ela envia os argumentos para a função para a pilha e, quando a função retorna, o faz poprando a pilha do programa.

Chris Bennet
fonte
7
Com a importante diferença de que a pilha de encadeamentos é severamente limitada e o algoritmo não recursivo usaria o heap muito mais escalável.
Yam Marcovic
1
Esta não é apenas uma situação artificial. Eu usei técnicas como essa em algumas ocasiões em C # e JavaScript para obter ganhos significativos de desempenho em relação aos equivalentes de chamadas recursivas existentes. Geralmente, o gerenciamento da recursão com uma pilha em vez de usar a pilha de chamadas é muito mais rápido e consome menos recursos. Há muita sobrecarga envolvida em colocar um contexto de chamada em uma pilha contra o programador poder tomar decisões práticas sobre o que colocar em uma pilha personalizada.
Jason Jackson
4

Uma implementação do ES6 com base na grande resposta do 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
fonte
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);

                }
            }

A lógica geral é empurrar um nó (começando da raiz) no valor Stack, Pop () it e Print (). Então, se houver filhos (esquerdo e direito), empurre-os para a pilha - empurre para a direita primeiro, para visitar o filho esquerdo primeiro (depois de visitar o próprio nó). Quando a pilha estiver vazia (), você terá visitado todos os nós na Pré-encomenda.

Sanj
fonte
2

DFS não recursivo usando geradores 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 
  }    
}

Ele se desvia do DFS não recursivo típico para detectar facilmente quando todos os descendentes alcançáveis ​​de um determinado nó foram processados ​​e para manter o caminho atual na lista / pilha.

Jarek Przygódzki
fonte
1

Suponha que você queira executar uma notificação quando cada nó em um gráfico for visitado. A implementação recursiva simples é:

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, agora você quer uma implementação baseada em pilha porque seu exemplo não funciona. Gráficos complexos podem, por exemplo, causar uma explosão na pilha do seu programa e você precisa implementar uma versão não recursiva. O maior problema é saber quando emitir uma notificação.

O pseudocódigo a seguir funciona (combinação de Java e C ++ para facilitar a leitura):

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, mas a lógica extra necessária para emitir notificações existe porque você precisa notificar em ordem inversa da visita - o DFS inicia na raiz, mas a notifica por último, ao contrário do BFS, que é muito simples de implementar.

Para chutes, tente o seguinte gráfico: os nós são s, t, vew. arestas direcionadas são: s-> t, s-> v, t-> w, v-> we v-> t. Execute sua própria implementação do DFS e a ordem na qual os nós devem ser visitados deve ser: w, t, v, s Uma implementação desajeitada do DFS talvez notifique primeiro t e isso indica um erro. Uma implementação recursiva do DFS sempre alcançaria w last.

user3804051
fonte
1

Exemplo de código de TRABALHO COMPLETO, sem pilha:

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

saída: Largura Primeiro Traversal - a partir do vértice 2: 2 0 3 1 4 Profundidade Primeiro Traversal - a partir do vértice 2: 2 3 4 1 0

Assaf Faybish
fonte
0

Você pode usar uma pilha. Implementei gráficos com 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();
        }
    }
}
noDispName
fonte
0

Iterativo DFS em 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
fonte
Pergunta pede explicitamente para um não binário árvore
user3743222
Você precisa de um mapa visitou para evitar loop infinito
spiralmoon
0

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

Acabei de assistir este vídeo e saiu com a implementação. Parece fácil para mim entender. Por favor, critique isso.

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
fonte
0

Usando Stack, aqui estão as etapas a seguir: Empurre o primeiro vértice da pilha e, em seguida,

  1. Se possível, visite um vértice não visitado adjacente, marque-o e empurre-o na pilha.
  2. Se você não pode seguir a etapa 1, se possível, retire um vértice da pilha.
  3. Se você não pode seguir as etapas 1 ou 2, está pronto.

Aqui está o programa Java seguindo as etapas acima:

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
fonte
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
fonte
0

Pseudo-código com base na resposta de @ biziclop:

  • Usando apenas construções básicas: variáveis, matrizes, se, enquanto e para
  • Funções getNode(id)egetChildren(id)
  • Supondo número conhecido de nós N

Observação: eu uso a indexação de matriz de 1, não 0.

Largura primeiro

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

Profundidade primeiro

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
fonte
0

Aqui está um link para um programa java que mostra o DFS seguindo métodos reccursivos e não reccursivos e também calculando o tempo de descoberta e de término , mas sem identificação de borda.

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

Fonte completa aqui .

Suhasis
fonte
0

Só queria adicionar minha implementação python à longa lista de soluções. Esse algoritmo não recursivo possui descoberta e eventos 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
fonte