广度优先bfs的python实现

广度优先搜索bfs的python实现

广度优先排序(BFS)可以一层一层地将图向外搜索, 以得到离起点最近的元素, 这个“最近”在不同情况可以有不同的意义

实现方法

将下一层所有元素先储存在同一个列表中, 当把本层元素的内容执行完后再执行.
还是以这张图为例:

当从s开始广度优先搜索时
第1层:[s]
第2层:[a,d]
第3层:[b,c]
第4层:[t]
依次执行这些列表就行了~
当然,这些列表可以合为一个处理, 即[s,a,d,b,c,t].这种情况通常用队列来处理, 但不好得到深度

通过leetcode127来实现广度优先搜索

代码如下

def ladderLength(self, beginWord, endWord, wordList):
	#beginWord = 'hit'
	#endWord = 'cog'
	#wordList = ['hot','dot','dog','lot','log','cog']
	
	#得到图
	tree = {}
	for i in wordList+[beginWord]:
	    length = len(i)
	    tree[i] = []
	    for j in wordList:
	        n=0
	        for u in range(length):
	            if j[u] == i[u]:
	                n+=1
	        if n+1 == length:
	            tree[i].append(j)
	            
	  #already = {}
	q = [beginWord]
	flag = 0
	while len(q):
	    flag += 1 #记录层数
	    nq = [] #记录下一层
	    for i in q:
	        if endWord == i:
	            return flag
	        for j in tree[i]:
	            #if not j in already: #避免重复, 节约时间, 但不会影响答案
	                #nq.append(j)
	                #already[j] =1
	            nq.append(j)
	    print(nq)
	    q = nq#改执行下一层
	return []

本文地址：https://blog.csdn.net/albert_fifth/article/details/110673290