Nierekurencyjny algorytm pierwszego wyszukiwania głębi

173

Szukam nierekurencyjnego algorytmu pierwszego wyszukiwania głębokości dla drzewa niebinarnego. Wszelaka pomoc jest bardzo doceniana.

mysi
źródło
1
@Bart Kiers Generalnie drzewo, sądząc po metce.
biziclop
13
Przeszukiwanie wgłębne jest algorytmem rekurencyjnym. Poniższe odpowiedzi rekurencyjnie eksplorują węzły, po prostu nie używają stosu wywołań systemu do wykonywania rekurencji i zamiast tego używają jawnego stosu.
Ustawiono
8
@Null Set Nie, to tylko pętla. Zgodnie z twoją definicją, każdy program komputerowy jest rekurencyjny. (Który w pewnym sensie tego słowa są.)
biziclop
1
@Null Set: Drzewo jest również cykliczną strukturą danych.
Gumbo
2
@MuhammadUmer Główną zaletą podejścia iteracyjnego w stosunku do podejść rekurencyjnych, gdy iteracja jest uważana za mniej czytelną, jest to, że można uniknąć ograniczeń maksymalnego rozmiaru stosu / głębokości rekurencji, które większość systemów / języków programowania implementuje w celu ochrony stosu. W stosie pamięci twój stos jest ograniczony tylko ilością pamięci, którą twój program może zużywać, co zazwyczaj pozwala na użycie stosu znacznie większego niż maksymalny rozmiar stosu wywołań.
John B

Odpowiedzi:

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
}

Symetria tych dwóch jest całkiem fajna.

Aktualizacja: jak wskazano, take_first()usuwa i zwraca pierwszy element z listy.

biziclop
źródło
11
+1 za zauważenie, jak podobne są te dwa, gdy są wykonywane nierekurencyjnie (jakby były radykalnie różne, gdy są rekurencyjne, ale nadal ...)
corsiKa
3
Następnie, aby dodać do symetrii, jeśli zamiast tego użyjesz kolejki o minimalnym priorytecie jako krawędzi, masz wyszukiwarkę najkrótszej ścieżki z jednego źródła.
Mark Peters
10
Nawiasem mówiąc, .first()funkcja usuwa również element z listy. Jak shift()w wielu językach. pop()działa również i zwraca węzły potomne w kolejności od prawej do lewej zamiast od lewej do prawej.
Ariel
5
IMO, algorytm DFS jest nieco niepoprawny. Wyobraź sobie 3 wierzchołki połączone ze sobą. Postęp powinien być: gray(1st)->gray(2nd)->gray(3rd)->blacken(3rd)->blacken(2nd)->blacken(1st). Ale kod produkuje: gray(1st)->gray(2nd)->gray(3rd)->blacken(2nd)->blacken(3rd)->blacken(1st).
batman
3
@learner Mogę źle rozumieć twój przykład, ale jeśli wszystkie są ze sobą połączone, to nie jest tak naprawdę drzewo.
biziclop,
40

Użyłbyś stosu, który zawiera węzły, które nie były jeszcze odwiedzane:

stack.push(root)
while !stack.isEmpty() do
    node = stack.pop()
    for each node.childNodes do
        stack.push(stack)
    endfor
    // …
endwhile
Gumbo
źródło
2
@Gumbo Zastanawiam się, czy to jest wykres z cyklami. Czy to działa? Myślę, że mogę po prostu uniknąć dodawania zdublowanego węzła do stosu i może to działać. To, co zrobię, to zaznaczenie wszystkich sąsiadów węzła, które zostały wyskakujące, i dodanie znaku, if (nodes are not marked)aby ocenić, czy jest odpowiedni do umieszczenia na stosie. Czy to zadziała?
Alston,
1
@Stallman Możesz zapamiętać węzły, które już odwiedziłeś. Jeśli wtedy odwiedzisz tylko węzły, których jeszcze nie odwiedziłeś, nie wykonasz żadnych cykli.
Gumbo
@Gumbo Co masz na myśli doing cycles? Myślę, że chcę tylko kolejność DFS. Czy to prawda, czy nie, dziękuję.
Alston,
Chciałem tylko podkreślić, że użycie stosu (LIFO) oznacza pierwsze przejście na głębokość. Jeśli chcesz użyć najpierw wszerz, użyj zamiast tego kolejki (FIFO).
Per Lundberg
3
Warto zauważyć, że aby mieć odpowiednik kodu jako najpopularniejszą odpowiedź @biziclop, należy przesuwać notatki potomne w odwrotnej kolejności ( for each node.childNodes.reverse() do stack.push(stack) endfor). Prawdopodobnie tego też chcesz. Ładne wyjaśnienie, dlaczego tak jest, jest w tym filmie: youtube.com/watch?v=cZPXfl_tUkA endfor
Mariusz Pawelski
32

Jeśli masz wskaźniki do węzłów nadrzędnych, 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

Zwróć uwagę, że jeśli węzły potomne są przechowywane jako tablica, a nie za pomocą wskaźników rodzeństwa, następny element siostrzany 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
aaz
źródło
Jest to dobre rozwiązanie, ponieważ nie wykorzystuje dodatkowej pamięci ani manipulowania listą lub stosem (kilka dobrych powodów, aby uniknąć rekursji). Jest to jednak możliwe tylko wtedy, gdy węzły drzewa mają linki do swoich rodziców.
joeytwiddle
Dziękuję Ci. Ten algorytm jest świetny. Ale w tej wersji nie można usunąć pamięci węzła w funkcji wizyty. Ten algorytm może konwertować drzewo do listy pojedynczo połączonej przy użyciu wskaźnika „first_child”. Możesz przez to przejść i zwolnić pamięć węzła bez rekursji.
puchu
6
„Jeśli masz wskaźniki do węzłów nadrzędnych, możesz to zrobić bez dodatkowej pamięci”: przechowywanie wskaźnika do węzłów nadrzędnych
zużywa
1
@ rptr87, jeśli nie jest jasne, bez dodatkowej pamięci poza tymi wskaźnikami.
Abhinav Gauniyal
To się nie powiedzie w przypadku częściowych drzew, w których węzeł nie jest absolutnym korzeniem, ale można go łatwo naprawić za pomocą while not node.next_sibling or node is root:.
Basel Shishani
5

Użyj stosu, aby śledzić swoje węzły

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
źródło
1
@Dave O. Nie, ponieważ wypychasz elementy podrzędne odwiedzanego węzła przed wszystko, co już tam jest.
biziclop
Musiałem wtedy źle zinterpretować semantykę funkcji push_back .
Dave O.
@Dave, masz bardzo dobry punkt widzenia. Pomyślałem, że powinno to być „wypychanie reszty kolejki z powrotem”, a nie „wypychanie w tył”. Poprawię odpowiednio.
corsiKa
Jeśli pchasz do przodu, powinien to być stos.
lot
@Timmy yeah Nie jestem pewien, o czym myślę. @quasiverse Zwykle myślimy o kolejce jak o kolejce FIFO. Stos jest definiowany jako kolejka LIFO.
corsiKa
4

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

Rekursja korzysta z wbudowanego stosu programów. Kiedy wywołujesz funkcję, wypycha ona argumenty funkcji na stos, a gdy funkcja zwraca, robi to, zdejmując stos programu.

Chris Bennet
źródło
7
Z tą ważną różnicą, że stos wątków jest poważnie ograniczony, a algorytm nierekurencyjny używałby znacznie bardziej skalowalnej sterty.
Yam Marcovic
1
To nie jest tylko wymyślona sytuacja. Używałem takich technik kilka razy w C # i JavaScript, aby uzyskać znaczący wzrost wydajności w porównaniu z istniejącymi rekursywnymi równoważnikami wywołań. Często zdarza się, że zarządzanie rekurencją za pomocą stosu zamiast używania stosu wywołań jest znacznie szybsze i mniej zasobochłonne. Umieszczenie kontekstu wywołania na stosie wiąże się z dużym narzutem, a programista nie jest w stanie podejmować praktycznych decyzji dotyczących tego, co umieścić na stosie niestandardowym.
Jason Jackson
4

Implementacja ES6 oparta na świetnej odpowiedzi 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
źródło
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);

                }
            }

Ogólna logika jest taka, że ​​wepchnij węzeł (zaczynając od katalogu głównego) do wartości Stack, Pop () it i Print (). Następnie, jeśli ma dzieci (lewe i prawe), wepchnij je do stosu - najpierw naciśnij Prawo, aby najpierw odwiedzić Lewe dziecko (po odwiedzeniu samego węzła). Gdy stos jest pusty (), odwiedzisz wszystkie węzły w przedsprzedaży.

Sanj
źródło
2

Nierekurencyjny system plików DFS przy użyciu generatorów 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 
  }    
}

Odchodzi od typowego nierekurencyjnego systemu plików DFS, aby łatwo wykryć, kiedy wszystkie osiągalne elementy potomne danego węzła zostały przetworzone i zachować bieżącą ścieżkę na liście / stosie.

Jarek Przygódzki
źródło
1

Załóżmy, że chcesz wykonać powiadomienie, gdy odwiedzany jest każdy węzeł na wykresie. 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 potrzebujesz implementacji opartej na stosie, ponieważ Twój przykład nie działa. Złożone wykresy mogą na przykład spowodować wysadzenie stosu twojego programu i musisz zaimplementować wersję nierekurencyjną. Największym problemem jest wiedzieć, kiedy wysłać powiadomienie.

Działa następujący pseudokod (mieszanka Java i C ++ dla czytelności):

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 na skomplikowane, ale dodatkowa logika potrzebna do wysyłania powiadomień istnieje, ponieważ musisz powiadamiać w odwrotnej kolejności odwiedzin - DFS uruchamia się u roota, ale powiadamia go na końcu, w przeciwieństwie do BFS, który jest bardzo prosty do wdrożenia.

W przypadku kopnięć spróbuj następującego wykresu: węzły to s, t, v i w. skierowane krawędzie to: s-> t, s-> v, t-> w, v-> w i v-> t. Uruchom własną implementację DFS i kolejność, w której węzły powinny być odwiedzane, musi być następująca: w, t, v, s Nieporadna implementacja DFS może najpierw powiadomić t, a to wskazuje na błąd. Rekurencyjna implementacja DFS zawsze osiągnęłaby ostatni.

user3804051
źródło
1

PEŁNY przykładowy kod ROBOCZY, bez stosu:

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

dane wyjściowe: Szerokość pierwszego przejścia - zaczynając od wierzchołka 2: 2 0 3 1 4 Głębokość pierwszego przejścia - zaczynając od wierzchołka 2: 2 3 4 1 0

Assaf Faybish
źródło
0

Możesz użyć stosu. Zaimplementowałem wykresy z 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
źródło
0

Iteracja DFS 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;
}
Piyush Patel
źródło
Pytanie wyraźnie prosi o drzewo binarne
user3743222,
Potrzebujesz odwiedzonej mapy, aby uniknąć nieskończonej pętli
spiralmoon
0

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

Właśnie obejrzałem ten film i wyszedłem z implementacją. Wydaje mi się, że łatwo to zrozumieć. Proszę, skrytykuj 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()
}
prog_guy
źródło
0

Używając Stack, oto kroki, które należy wykonać: Wepchnij pierwszy wierzchołek stosu, a następnie

  1. Jeśli to możliwe, odwiedź sąsiedni nieodwiedzony wierzchołek, zaznacz go i wepchnij na stos.
  2. Jeśli nie możesz wykonać kroku 1, jeśli to możliwe, zdejmij wierzchołek ze stosu.
  3. Jeśli nie możesz wykonać kroku 1 lub kroku 2, gotowe.

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;
}
Yogesh Umesh Vaity
źródło
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
źródło
0

Pseudokod oparty na odpowiedzi @ biziclop:

  • Używając tylko podstawowych konstrukcji: zmiennych, tablic, if, while i for
  • Funkcje getNode(id)igetChildren(id)
  • Zakładając znaną liczbę węzłów N

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

Wszerz

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

Najpierw głębia

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.
źródło
0

Tutaj jest link do programu java pokazującego DFS stosujący zarówno metody rekurencyjne, jak i nierekurencyjne, a także obliczający czas wykrywania i zakończenia , ale bez lalkowania na krawędzi.

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

Pełne źródło tutaj .

Suhasis
źródło
0

Chciałem tylko dodać moją implementację Pythona do długiej listy rozwiązań. Ten nierekurencyjny algorytm wykrył i zakończył zdarzenia.


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
źródło