Нерекурсивный алгоритм поиска по глубине

173

Я ищу нерекурсивный алгоритм поиска в глубину для недвоичного дерева. Любая помощь очень ценится.

робкий
источник
1
@Bart Kiers Дерево в общем, судя по тегу.
biziclop
13
Глубина первого поиска - рекурсивный алгоритм. Ответы ниже рекурсивно исследуют узлы, они просто не используют системный стек вызовов для выполнения своей рекурсии и вместо этого используют явный стек.
Нулевой сет
8
@Null Set Нет, это просто цикл. По вашему определению, каждая компьютерная программа является рекурсивной. (Которые, в определенном смысле слова, они есть.)
biziclop
1
@Null Set: дерево также является рекурсивной структурой данных.
Гамбо
2
@MuhammadUmer Основное преимущество итеративного подхода по сравнению с рекурсивным, когда итеративный подход считается менее читабельным, заключается в том, что вы можете избежать ограничений максимального размера стека / глубины рекурсии, которые большинство систем / языков программирования реализуют для защиты стека. При наличии стека в памяти ваш стек ограничен только объемом памяти, который разрешено использовать вашей программе, что, как правило, позволяет стеку намного превышать максимальный размер стека вызовов.
Джон Б,

Ответы:

313

ДФС:

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
}

Симметрия двух довольно крутая.

Обновление: как указано, take_first()удаляет и возвращает первый элемент в списке.

biziclop
источник
11
+1 за то, что отметили, насколько похожи эти два, когда они сделаны нерекурсивно (как будто они радикально отличаются, когда они рекурсивны, но все же ...)
corsiKa
3
И затем, чтобы добавить к симметрии, если вы вместо этого используете очередь с минимальным приоритетом, у вас есть поиск кратчайшего пути из одного источника.
Марк Питерс
10
Кстати, .first()функция также удаляет элемент из списка. Как и shift()во многих языках. pop()также работает и возвращает дочерние узлы в порядке справа налево вместо слева направо.
Ариэль
5
ИМО, алгоритм DFS немного некорректен. Вообразите 3 вершины, все соединенные друг с другом. Прогресс должен быть: gray(1st)->gray(2nd)->gray(3rd)->blacken(3rd)->blacken(2nd)->blacken(1st). Но ваш код производит: gray(1st)->gray(2nd)->gray(3rd)->blacken(2nd)->blacken(3rd)->blacken(1st).
Бэтмен
3
@learner Возможно, я неправильно понимаю ваш пример, но если они все связаны друг с другом, это не совсем дерево.
Бизиклоп
40

Вы бы использовали стек, который содержит узлы, которые еще не были посещены:

stack.push(root)
while !stack.isEmpty() do
    node = stack.pop()
    for each node.childNodes do
        stack.push(stack)
    endfor
    // …
endwhile
гумбо
источник
2
@ Гамбо Мне интересно, если это график с цицилами. Может ли это работать? Я думаю, что я могу просто избежать добавления дублированного узла в стек, и он может работать. То, что я сделаю, это отметит всех соседних узлов, которые выскочили, и добавит a, if (nodes are not marked)чтобы судить, подходит ли это для помещения в стек. Может ли это работать?
Алстон
1
@ Stallman Вы можете вспомнить узлы, которые вы уже посетили. Если вы затем посещаете только те узлы, которые еще не посещали, вы не будете делать никаких циклов.
Гамбо
@ Гамбо Что ты имеешь в виду doing cycles? Я думаю, что я просто хочу заказать DFS. Это правильно или нет, спасибо.
Алстон
Просто хотел бы отметить, что использование стека (LIFO) означает прохождение в глубину. Если вы хотите использовать ширину в первую очередь, вместо этого используйте очередь (FIFO).
За Лундберг
3
Стоит отметить, что для того, чтобы иметь эквивалентный код в качестве самого популярного ответа @biziclop, вам нужно помещать дочерние заметки в обратном порядке ( for each node.childNodes.reverse() do stack.push(stack) endfor). Это также, вероятно, то, что вы хотите. Хорошее объяснение, почему это так, в этом видео: youtube.com/watch?v=cZPXfl_tUkA endfor
Мариуш Павельски
32

Если у вас есть указатели на родительские узлы, вы можете сделать это без дополнительной памяти.

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

Обратите внимание, что если дочерние узлы хранятся в виде массива, а не с помощью указателей на одноуровневый элемент, следующий одноуровневый элемент может быть найден как:

def next_sibling(node):
    try:
        i =    node.parent.child_nodes.index(node)
        return node.parent.child_nodes[i+1]
    except (IndexError, AttributeError):
        return None
Ааз
источник
Это хорошее решение, потому что оно не использует дополнительную память или манипулирование списком или стеком (некоторые веские причины, чтобы избежать рекурсии). Однако это возможно только в том случае, если узлы дерева имеют ссылки на своих родителей.
Joeytwiddle
Спасибо. Этот алгоритм великолепен. Но в этой версии вы не можете удалить память узла в функции посещения. Этот алгоритм может преобразовать дерево в односвязный список с помощью указателя «first_child». Чем вы можете пройти через него и освободить память узла без рекурсии.
Пучу
6
«Если у вас есть указатели на родительские узлы, вы можете сделать это без дополнительной памяти»: хранение указателя на родительские узлы действительно использует некоторую «дополнительную память» ...
rptr
1
@ rptr87, если неясно, без дополнительной памяти, кроме этих указателей.
Абхинав Гауниал,
Это не удастся для частичных деревьев, где узел не является абсолютным корнем, но может быть легко исправлен while not node.next_sibling or node is root:.
Базель Шишани
5

Используйте стек для отслеживания ваших узлов

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
источник
1
@ Дэйв О. Нет, потому что вы отталкиваете потомков посещенного узла перед всем, что уже есть.
Бизиклоп
Должно быть, я неправильно истолковал семантику push_back .
Дейв О.
@ У тебя есть очень хорошая мысль. Я думал, что это должно быть «отталкивание остальной части очереди назад», а не «отталкивание назад». Я буду редактировать соответственно.
CorsiKa
Если вы толкаете вперед, это должен быть стек.
рейс
@ Тимми, да, я не уверен, что я там думал. @quasiverse Обычно мы рассматриваем очередь как очередь FIFO. Стек определяется как очередь LIFO.
CorsiKa
4

Хотя «использовать стек» может работать как ответ на надуманный вопрос об интервью, на самом деле он просто делает явно то, что делает за кулисами рекурсивная программа.

Рекурсия использует встроенный в стек программы. Когда вы вызываете функцию, она помещает аргументы функции в стек, а когда функция возвращает это, она выталкивает программный стек.

Крис Беннет
источник
7
С важной разницей, что стек потоков строго ограничен, а нерекурсивный алгоритм будет использовать гораздо более масштабируемую кучу.
Ям Маркович
1
Это не просто надуманная ситуация. Я несколько раз использовал подобные методы в C # и JavaScript, чтобы добиться значительного прироста производительности по сравнению с существующими рекурсивными вызовами. Часто бывает так, что управление рекурсией с помощью стека вместо использования стека вызовов происходит намного быстрее и требует меньше ресурсов. Существует много накладных расходов, связанных с размещением контекста вызова в стеке, поскольку программист может принимать практические решения о том, что поместить в пользовательский стек.
Джейсон Джексон
4

Реализация ES6 на основе 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);
  }
}

Макс Лейзерович
источник
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);

                }
            }

Общая логика заключается в том, чтобы вставить узел (начиная с корня) в значение Stack, Pop () it и Print (). Затем, если у него есть дочерние элементы (левый и правый), поместите их в стек - сначала нажмите «Вправо», чтобы сначала вы посетили «Левый потомок» (после посещения самого узла). Когда стек пуст (), вы посетили все узлы в предзаказе.

Sanj
источник
2

Нерекурсивная DFS с использованием генераторов 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 
  }    
}

Он отличается от типичной нерекурсивной DFS, чтобы легко обнаруживать, когда были обработаны все достижимые потомки данного узла, и поддерживать текущий путь в списке / стеке.

Ярек Пшигодзки
источник
1

Предположим, вы хотите выполнить уведомление при посещении каждого узла в графике. Простая рекурсивная реализация:

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
}

Хорошо, теперь вам нужна реализация на основе стека, потому что ваш пример не работает. Сложные графики могут, например, привести к тому, что это разрушит стек вашей программы, и вам нужно реализовать нерекурсивную версию. Самая большая проблема заключается в том, чтобы знать, когда выдать уведомление.

Следующий псевдокод работает (смесь Java и C ++ для удобства чтения):

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

Это выглядит сложным, но дополнительная логика, необходимая для выдачи уведомлений, существует, потому что вы должны уведомлять в обратном порядке посещения - DFS запускается с правами root, но уведомляет его последним, в отличие от BFS, который очень прост в реализации.

Для ударов попробуйте следующий график: узлами являются s, t, v и w. Направленные ребра: s-> t, s-> v, t-> w, v-> w и v-> t. Запустите собственную реализацию DFS, и порядок посещения узлов должен быть следующим: w, t, v, s. Неуклюжая реализация DFS может сначала уведомить t, что указывает на ошибку. Рекурсивная реализация DFS всегда доходила бы до последней.

user3804051
источник
1

ПОЛНЫЙ пример РАБОЧИЙ код без стека:

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

Вывод: Первый обход ширины - начиная с вершины 2: 2 0 3 1 4 Первый обход глубины - начиная с вершины 2: 2 3 4 1 0

Ассаф Файбиш
источник
0

Вы можете использовать стек. Я реализовал графики с помощью матрицы смежности:

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
источник
0

DFS итеративный в 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;
}
Пиюш Патель
источник
Вопрос явно задает недвоичное дерево
user3743222
Вам нужна посещенная карта, чтобы избежать бесконечного цикла
spiralmoon
0

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

Просто посмотрел это видео и вышел с реализацией. Это выглядит легко для меня, чтобы понять. Пожалуйста, критикуйте это.

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
источник
0

Используя Stack, вот шаги, чтобы следовать: толкните первую вершину в стеке, затем,

  1. Если возможно, посетите соседнюю не посещенную вершину, отметьте ее и поместите в стек.
  2. Если вы не можете выполнить шаг 1, тогда, если возможно, вытолкните вершину из стека.
  3. Если вы не можете выполнить шаг 1 или шаг 2, все готово.

Вот Java-программа, выполняющая следующие шаги:

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;
}
Йогеш Умеш Ваиты
источник
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
источник
0

Псевдокод, основанный на ответе @ biziclop:

  • Использование только базовых конструкций: переменных, массивов, если, в то время и для
  • Функции getNode(id)иgetChildren(id)
  • Предполагая известное количество узлов N

ПРИМЕЧАНИЕ: я использую индексирование массива от 1, а не от 0.

Ширина-первых

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

Глубина первой

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
Джонатан Х
источник
0

Вот ссылка на Java-программу, показывающую DFS, которая следует как рекурсивным, так и нерекурсивным методам, а также вычисляет время обнаружения и завершения , но без краевого лалерования.

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

Полный источник здесь .

Suhasis
источник
0

Просто хотел добавить мою реализацию Python в длинный список решений. Этот нерекурсивный алгоритм имеет обнаружение и завершенные события.


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
источник