在 python 中优化广度优先搜索

Question

我写了一个深度优先搜索，returns 找到目标节点的深度，如果没有找到路径，则为 -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

在 python 中优化广度优先搜索

optimizing breadth first search in python

python

graph

breadth-first-search