Come tenere traccia della profondità nella prima ricerca?

Question

Ho un albero come input per la prima ricerca di larghezza e voglio sapere come l'algoritmo progredisce a che livello è?

# 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') 

Prende albero come un grafo di input, quello che voglio è che ad ogni iterazione dovrebbe stampare il livello di corrente che si elabora.

Answer 1

Prova a dare un'occhiata a questo post. Tiene traccia della profondità usando la variabile currentDepth

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

Per la vostra applicazione, tenere traccia dei più nodo di sinistra e una variabile per la profondità. Ogni volta che il nodo più a sinistra viene estratto dalla coda, sai di aver raggiunto un nuovo livello e di aumentare la profondità.

Quindi, la tua radice è la leftMostNode al livello 0. Quindi il bambino più a sinistra è lo leftMostNode. Non appena lo colpisci, diventa livello 1. Il figlio più a sinistra di questo nodo è il prossimo leftMostNode e così via.

Answer 2

Mantiene una coda che memorizza la profondità del nodo corrispondente nella coda BFS. Codice di esempio per vostra informazione:

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

Questo metodo è semplice e ingenuo, per O (1) spazio in più potrebbe essere necessario il palo risposta da @stolen_leaves.

Answer 3

Non è necessario utilizzare la coda aggiuntiva o eseguire calcoli complicati per ottenere ciò che si desidera fare. Questa idea è molto semplice.

Questo non utilizza altro spazio oltre alla coda utilizzata per BFS.

L'idea che sto per utilizzare è aggiungere null alla fine di ogni livello. Quindi il numero di null che hai incontrato +1 è la profondità a cui sei. (ovviamente dopo la risoluzione è solo 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); 
    }