Algoritma pencarian pertama kedalaman non-rekursif

Saya mencari algoritma pencarian kedalaman non-rekursif pertama untuk pohon non-biner. Bantuan apa pun sangat kami hargai.

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
}

Simetri keduanya cukup keren.

Pembaruan: Seperti yang ditunjukkan, take_first()menghapus dan mengembalikan elemen pertama dalam daftar.

Anda akan menggunakan tumpukan yang menyimpan simpul-simpul yang belum dikunjungi:

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

Jika Anda memiliki pointer ke node induk, Anda dapat melakukannya tanpa memori tambahan.

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

Perhatikan bahwa jika child node disimpan sebagai array alih-alih melalui sibling pointer, saudara berikutnya dapat ditemukan sebagai:

def next_sibling(node):
    try:
        i =    node.parent.child_nodes.index(node)
        return node.parent.child_nodes[i+1]
    except (IndexError, AttributeError):
        return None

Gunakan tumpukan untuk melacak node Anda

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)

}

Meskipun "menggunakan tumpukan" mungkin berfungsi sebagai jawaban untuk pertanyaan wawancara yang dibuat-buat, pada kenyataannya, itu hanya melakukan secara eksplisit apa yang dilakukan oleh program rekursif di belakang layar.

Rekursi menggunakan stack bawaan program. Ketika Anda memanggil fungsi, itu mendorong argumen ke fungsi ke stack dan ketika fungsi mengembalikannya melakukannya dengan membuka tumpukan program.

Implementasi ES6 berdasarkan jawaban hebat 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);
  }
}

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

                }
            }

Logikanya umum adalah, dorong sebuah simpul (mulai dari root) ke nilai Stack, Pop () dan Print (). Kemudian jika memiliki anak (kiri dan kanan) dorong mereka ke tumpukan - dorong Kanan terlebih dahulu sehingga Anda akan mengunjungi Kiri anak terlebih dahulu (setelah mengunjungi simpul itu sendiri). Ketika tumpukan kosong () Anda akan mengunjungi semua simpul di Pra-Pemesanan.

DFS non-rekursif menggunakan generator 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 
  }    
}

Ini menyimpang dari DFS non-rekursif khas untuk dengan mudah mendeteksi ketika semua keturunan yang terjangkau dari node yang diberikan diproses dan untuk mempertahankan jalur saat ini dalam daftar / tumpukan.

Misalkan Anda ingin menjalankan notifikasi ketika setiap node dalam grafik dikunjungi. Implementasi rekursif sederhana adalah:

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
}

Oke, sekarang Anda menginginkan implementasi berbasis stack karena contoh Anda tidak berfungsi. Grafik kompleks mungkin misalnya menyebabkan ini untuk meniup tumpukan program Anda dan Anda perlu menerapkan versi non-rekursif. Masalah terbesar adalah mengetahui kapan harus mengeluarkan pemberitahuan.

Kode pseudo berikut berfungsi (campuran Java dan C ++ untuk keterbacaan):

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

Itu terlihat rumit tetapi logika tambahan yang diperlukan untuk mengeluarkan pemberitahuan ada karena Anda perlu memberi tahu dengan urutan kunjungan yang terbalik - DFS dimulai pada saat root tetapi memberi tahu yang terakhir, tidak seperti BFS yang sangat mudah diterapkan.

Untuk tendangan, coba grafik berikut: node adalah s, t, v dan w. tepi diarahkan adalah: s-> t, s-> v, t-> w, v-> w, dan v-> t. Jalankan implementasi DFS Anda sendiri dan urutan node yang harus dikunjungi harus: w, t, v, s Implementasi DFS yang canggung mungkin akan memberi tahu t terlebih dahulu dan itu menunjukkan bug. Implementasi DFS secara rekursif akan selalu mencapai yang terakhir.

Contoh lengkap kode KERJA, tanpa tumpukan:

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

output: Breadth First Traversal- mulai dari vertex 2: 2 0 3 1 4 Kedalaman First Traversal- mulai dari vertex 2: 2 3 4 1 0

Anda dapat menggunakan tumpukan. Saya menerapkan grafik dengan 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();
        }
    }
}

Berulang DFS di Jawa:

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

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

Baru saja menonton video ini dan keluar dengan implementasi. Tampaknya mudah bagi saya untuk mengerti. Tolong kritik ini.

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

Dengan menggunakan Stack, berikut adalah langkah-langkah yang harus diikuti: Dorong titik pertama pada tumpukan lalu,

1. Jika memungkinkan, kunjungi verteks yang belum dikunjungi yang berdekatan, tandai, dan dorong pada tumpukan.
2. Jika Anda tidak dapat mengikuti langkah 1, maka, jika mungkin, keluarkan sebuah simpul dari tumpukan.
3. Jika Anda tidak dapat mengikuti langkah 1 atau langkah 2, Anda selesai.

Inilah program Java yang mengikuti langkah-langkah di atas:

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

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

Kode semu berdasarkan pada jawaban @ biziclop:

• Hanya menggunakan konstruksi dasar: variabel, array, jika, sementara dan untuk
• Fungsi getNode(id)dangetChildren(id)
• Dengan asumsi jumlah node yang diketahui N

CATATAN: Saya menggunakan array-indexing dari 1, bukan 0.

Luasnya pertama

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

Kedalaman-pertama

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

Berikut ini adalah tautan ke program java yang menampilkan DFS mengikuti metode rekcursive dan non-reccursive dan juga menghitung waktu penemuan dan penyelesaian , tetapi tidak ada edge laleling.

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

Sumber lengkap di sini .

Hanya ingin menambahkan implementasi python saya ke daftar panjang solusi. Algoritma non-rekursif ini memiliki penemuan dan penyelesaian peristiwa.

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)