在python中优化广度优先搜索

Question

我已经编写了一个深度优先搜索，该深度优先搜索返回发现目标节点的深度，如果找不到路径，则返回-1。该算法的工作原理，但我需要加快。下面是在声明

dic = defaultdict(list) 

，以便每个值是整数列表和我使用的传递函数

def depth(dic, head, target): 
    if(head==target): 
     return 
    depth=1 
    que = deque() 
    que.append('|') #used to mark end of each breadth so i can count depth correctly 
    used = list() 
    add = True 

    while(que): #while the que isn't empty 
     for x in dic[head]: #check current level 
      if x==target: 
       print(depth), 
       return; 
     for x in dic[head]: #add this level to the que and used list 
      for y in used: 
       if y==x: 
        add=False 
        break 
      if add == True: 
       que.append(x) 
       used.append(x) 
      add=True 
     que.append('|') #add our delimiter 
     while(que): #grab the next item from the que and inc depth count 
      temp = que.popleft() 
      if temp=='|': #bump depth counter since we found end of a level 
       depth+=1 
      else: 
       head=temp #bump to next node to check 
       break 

    print('-1'), #reached the end, node not found 

的DIC |所以我知道什么时候撞到深度计数器。我意识到我陷入了中间，我正在检查当前级别的所有节点，并将它们添加到que和used列表中，但我不知道如何加快速度。

编辑：

的人，这里也有类似的问题是，我结束了与算法，它通过搜索步骤的方式有点奇怪，因为我回来最浅的深度处的值可以发现，如果在同一深度不是所有连接在我们最终可能会（通过一个错误，如关闭）下一个深度找到的节点同时进行了检查

def depthOfNodeBFS(dic, head, target): 
    if(head==target): 
     return 
    depth=0 
    que = [] 
    que.append(head) 
    used = set() 
    nex = list() 

    while(que): #while the que isn't empty 
     depth+=1 #bump the depth counter 
     for x in que: #check the next level of all nodes at current depth 
      if target in dic[x]: #if the target is found were done 
       print(depth), 
       return; 
      else:    #other wise track what we've checked 
       nex.append(x) 
       used.add(x) 
     while(nex):  #remove checked from que and add children to que 
      que.pop(0) 
      que.extend(dic[nex.pop()]-used) 
    print('-1'), 

Answer 1

这看起来更像是广度优先搜索深度优先搜索给我，但你不应该嵌套while循环。通常的算法广度优先搜索是一样的东西：

add the root to the queue 
while the queue is not empty: 
    dequeue the first element elt 
    if elt is the solution, return it 
    otherwise, add each child of elt to the queue 

如果您要举报的深度，我建议加元组（节点，深度）队列：

add (root, 0) to the queue 
while the queue is not empty: 
    elt, depth = queue.popleft() 
    if elt is the solution, return (elt, depth) 
    otherwise, for each child of elt: 
    add (child, depth+1) to the queue