我写了一个深度优先搜索,它返回找到目标节点的深度,如果没有找到路径,返回-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被声明
^{pr2}$所以每个值都是一个整数的列表,我使用|这样我就知道什么时候该触发深度计数器了。我意识到我在中间陷入了困境,我要检查当前级别的所有节点并将它们添加到que和used列表中,但是我不知道如何加快速度。在
编辑:
对于任何有类似问题的人来说,这就是我最后得出的算法,它逐步搜索的方式有点奇怪,因为我返回的是可以找到值的最浅深度,如果不是在同一时间检查同一深度的所有连接,我们可能最终在下一个深度找到节点(就像一个off-by-one错误)
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'),
在我看来,这更像是广度优先搜索,而不是深度优先搜索,但是您不应该嵌套
while
循环。宽度优先搜索的常用算法如下:如果要报告深度,我建议向队列添加元组(node,depth):
^{pr2}$相关问题 更多 >
编程相关推荐