python - 优化Python中的广度优先搜索

Question

我编写了一个深度优先搜索，它返回找到目标节点的深度，如果没有找到路径，则返回 -1。该算法有效，但我需要加快速度。这是函数

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

dic = defaultdict(list)

这样每个值都是一个整数列表，我正在使用 |所以我知道什么时候该调整深度计数器。我意识到我陷入了中间，我正在检查当前级别的所有节点并将它们添加到队列和使用列表中，但我不知道如何加快速度。

编辑:

对于任何有类似问题的人来说，这里是我最终得到的算法，它逐步执行搜索的方式有点奇怪，因为我返回的是可以找到值的最浅深度，如果不是全部的话同时检查相同深度的连接，我们最终可能会找到下一个深度的节点(就像一个错误)

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