wake-up-neo.com

Wie kann man die Tiefe bei der ersten Suche nachverfolgen?

Ich habe einen Baum als Eingabe für die Breitensuche und möchte wissen, wie der Algorithmus vorgeht, auf welcher Ebene er sich befindet?

# Breadth First Search Implementation
graph = { 
    'A':['B','C','D'],
    'B':['A'],
    'C':['A','E','F'],
    'D':['A','G','H'],
    'E':['C'],
    'F':['C'],
    'G':['D'],
    'H':['D']
    }


def breadth_first_search(graph,source):
    """
    This function is the Implementation of the breadth_first_search program
    """
    # Mark each node as not visited
    mark = {}
    for item in graph.keys():
        mark[item] = 0

    queue, output = [],[]

    # Initialize an empty queue with the source node and mark it as explored
    queue.append(source)
    mark[source] = 1
    output.append(source)

    # while queue is not empty
    while queue:
        # remove the first element of the queue and call it vertex
        vertex = queue[0]
        queue.pop(0)
        # for each Edge from the vertex do the following
        for vrtx in graph[vertex]:
            # If the vertex is unexplored
            if mark[vrtx] == 0:
                queue.append(vrtx)  # mark it as explored
                mark[vrtx] = 1      # and append it to the queue
                output.append(vrtx) # fill the output vector
    return output

print breadth_first_search(graph, 'A')

Es ist Baum als Eingabegraph. Ich möchte, dass bei jeder Iteration die aktuelle Ebene gedruckt wird, die gerade verarbeitet wird.

13
functioncall

Sie müssen keine zusätzliche Warteschlange verwenden oder komplizierte Berechnungen durchführen, um das zu erreichen, was Sie möchten. Diese Idee ist sehr einfach.

Dies verwendet keinen zusätzlichen Speicherplatz außer der für BFS verwendeten Warteschlange.

Die Idee, die ich verwenden werde, ist, am Ende jedes Levels null hinzuzufügen. Die Anzahl der Nullen, denen Sie +1 begegnet sind, ist also die Tiefe, in der Sie sich befinden. (Natürlich ist es nach der Kündigung nur level). 

     int level = 0;
     Queue <Node> queue = new LinkedList<>();
     queue.add(root);
     queue.add(null);
     while(!queue.isEmpty()){
          Node temp = queue.poll();
          if(temp == null){
              level++;
              queue.add(null);
              if(queue.peek() == null) break;// You are encountering two consecutive `nulls` means, you visited all the nodes.
              else continue;
          }
          if(temp.right != null)
              queue.add(temp.right);
          if(temp.left != null)
              queue.add(temp.left);
     }
28
Karthik

Pflegen Sie eine Warteschlange, in der die Tiefe des entsprechenden Knotens in der BFS-Warteschlange gespeichert ist. Beispielcode zu Ihrer Information:

queue bfsQueue, depthQueue;
bfsQueue.Push(firstNode);
depthQueue.Push(0);
while (!bfsQueue.empty()) {
    f = bfsQueue.front();
    depth = depthQueue.front();
    bfsQueue.pop(), depthQueue.pop();
    for (every node adjacent to f) {
        bfsQueue.Push(node), depthQueue.Push(depth+1);
    } 
}

Diese Methode ist einfach und naiv, für O(1) zusätzlichen Speicherplatz benötigen Sie möglicherweise den Antwortpost von @stolen_leaves.

4
matrixit

Wenn Ihr Baum perfekt ausbalanciert ist (d. H. Jeder Knoten hat die gleiche Anzahl von Kindern), gibt es hier eine einfache, elegante Lösung mit O(1) Zeitkomplexität und O(1) Raumkomplexität. Die Hauptanwendung, bei der ich dies hilfreich finde, ist das Durchqueren eines binären Baums, obwohl er trivial an andere Baumgrößen anpassbar ist.

Der Schlüssel ist dabei zu erkennen, dass jede Ebene eines binären Baums genau doppelt so viele Knoten enthält wie die vorherige Ebene. Auf diese Weise können wir die Gesamtanzahl der Knoten in einem Baum unter Berücksichtigung der Baumtiefe berechnen. Betrachten Sie zum Beispiel den folgenden Baum:

 enter image description here

Dieser Baum hat eine Tiefe von 3 und 7 Gesamtknoten. Wir müssen die Anzahl der Knoten jedoch nicht zählen, um dies herauszufinden. Wir können dies in der Zeit O(1) mit der Formel berechnen: 2 ^ d - 1 = N, wobei d die Tiefe und N die Gesamtanzahl der Knoten ist. (In einem ternären Baum ist dies 3 ^ d - 1 = N, und in einem Baum, in dem jeder Knoten K Kinder hat, ist dies K ^ d - 1 = N). In diesem Fall also 2 ^ 3 - 1 = 7.

Um die Tiefe während der ersten Breitensuche zu verfolgen, ist wir müssen nur diese Berechnung umkehren. Während die obige Formel es uns erlaubt, für N gegebene d zu lösen, wollen wir eigentlich für d gegebene N lösen. Nehmen wir zum Beispiel an, wir bewerten den 5. Knoten. Um herauszufinden, in welcher Tiefe sich der fünfte Knoten befindet, nehmen wir die folgende Gleichung: 2 ^ d - 1 = 5 und dann lösen Sie einfach nach d, was grundlegende Algebra ist:

 enter image description here

Wenn sich d als etwas anderes als eine ganze Zahl herausstellt, runden Sie einfach auf (der letzte Knoten in einer Zeile ist immer eine ganze Zahl). Vor diesem Hintergrund schlage ich den folgenden Algorithmus vor, um die Tiefe eines bestimmten Knotens in einem Binärbaum während des ersten Durchlaufs zu ermitteln:

  1. Sei die Variable visited gleich 0.
  2. Erhöhen Sie jedes Mal, wenn ein Knoten besucht wird, visited um 1.
  3. Jedes Mal, wenn visited inkrementiert wird, berechnen Sie die Tiefe des Knotens als depth = round_up(log2(visited + 1)).

Sie können auch eine Hashtabelle verwenden, um jeden Knoten seiner Tiefenebene zuzuordnen. Dies erhöht jedoch die Komplexität des Speicherplatzes um O (n). Hier ist eine PHP Implementierung dieses Algorithmus:

<?php
$tree = [
    ['A', [1,2]],
    ['B', [3,4]],
    ['C', [5,6]],
    ['D', [7,8]],
    ['E', [9,10]],
    ['F', [11,12]],
    ['G', [13,14]],
    ['H', []],
    ['I', []],
    ['J', []],
    ['K', []],
    ['L', []],
    ['M', []],
    ['N', []],
    ['O', []],
];

function bfs($tree) {
    $queue = new SplQueue();
    $queue->enqueue($tree[0]);
    $visited = 0;
    $depth = 0;
    $result = [];

    while ($queue->count()) {

        $visited++;
        $node = $queue->dequeue();
        $depth = ceil(log($visited+1, 2));
        $result[$depth][] = $node[0];


        if (!empty($node[1])) {
            foreach ($node[1] as $child) {
                $queue->enqueue($tree[$child]);
            }
        }
    }
    print_r($result);
}

bfs($tree);

Welche drucke:

    Array
    (
        [1] => Array
            (
                [0] => A
            )

        [2] => Array
            (
                [0] => B
                [1] => C
            )

        [3] => Array
            (
                [0] => D
                [1] => E
                [2] => F
                [3] => G
            )

        [4] => Array
            (
                [0] => H
                [1] => I
                [2] => J
                [3] => K
                [4] => L
                [5] => M
                [6] => N
                [7] => O
            )

    )
3
Matt Korostoff

Schauen Sie sich diesen Beitrag an. Es verfolgt die Tiefe mit der Variablen currentDepth

https://stackoverflow.com/a/16923440/3114945

Behalten Sie für Ihre Implementierung den Knoten ganz links und eine Variable für die Tiefe im Auge. Immer wenn der am weitesten links liegende Knoten aus der Warteschlange entfernt wird, wissen Sie, dass Sie eine neue Ebene erreicht haben und erhöhen die Tiefe.

Ihre Wurzel ist also die leftMostNode auf Stufe 0. Dann ist das am weitesten links stehende Kind die leftMostNode. Sobald Sie es treffen, wird es auf Stufe 1. Das am weitesten links stehende Kind dieses Knotens ist die nächste leftMostNode und so weiter. 

3
stolen_leaves

Mit diesem Python-Code können Sie die Tiefe jedes Knotens von der Wurzel aus beibehalten, indem Sie die Tiefe erst erhöhen, nachdem Sie einen Knoten mit neuer Tiefe in der Warteschlange gefunden haben.

    queue = deque()
    marked = set()
    marked.add(root)
    queue.append((root,0))

    depth = 0
    while queue:
        r,d = queue.popleft()
        if d > depth: # increase depth only when you encounter the first node in the next depth               
            depth += 1
        for node in edges[r]:
            if node not in marked:
                marked.add(node)
                queue.append((node,depth+1))
1
MROB

Tatsächlich benötigen wir weder eine zusätzliche Warteschlange zum Speichern der Tiefe noch müssen wir null hinzufügen, um festzustellen, ob das aktuelle Level zu Ende ist. Wir müssen nur wissen, wie viele Knoten die aktuelle Ebene hat, dann können wir uns mit allen Knoten in derselben Ebene befassen und die Ebene um 1 erhöhen, nachdem wir fertig sind.

int level = 0;
Queue<Node> queue = new LinkedList<>();
queue.add(root);
while(!queue.isEmpty()){
    int level_size = queue.size();
    while (level_size--) {
        Node temp = queue.poll();
        if (temp.right != null) queue.add(temp.right);
        if (temp.left != null) queue.add(temp.left);
    }    
    level++;
}
1
KDD

In Java wäre dies ungefähr so ​​.. Die Idee ist, die übergeordnete Komponente zu betrachten, um die Tiefe festzulegen. 

//Maintain depth for every node based on its parent's depth
Map<Character,Integer> depthMap=new HashMap<>();    

queue.add('A');
depthMap.add('A',0); //this is where you start your search

while(!queue.isEmpty())
{
   Character parent=queue.remove();
   List<Character> children=adjList.get(parent);
   for(Character c:children)
   {
      depthMap.add(c,depthMap.get(parent)+1);//parent's depth + 1

   }

}
0
developer747

Ich schreibe einen einfachen und leicht lesbaren Code in Python.

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def dfs(self, root):
        assert root is not None
        queue = [root]
        level = 0
        while queue:
            print(level, [n.val for n in queue if n is not None])
            mark = len(queue)
            for i in range(mark):
                n = queue[i]
                if n.left is not None:
                    queue.append(n.left)
                if n.right is not None:
                    queue.append(n.right)
            queue = queue[mark:]
            level += 1

Verwendungszweck,

# [3,9,20,null,null,15,7]
n3 = TreeNode(3)
n9 = TreeNode(9)
n20 = TreeNode(20)
n15 = TreeNode(15)
n7 = TreeNode(7)
n3.left = n9
n3.right = n20
n20.left = n15
n20.right = n7
DFS().dfs(n3)

Ergebnis

0 [3]
1 [9, 20]
2 [15, 7]
0
s-han.lee