无向图的广度优先搜索

无向图的广度优先搜索

graph = {}
graph['wt'] = ['a', 'b', 'c']
graph['a'] = ['d']
graph['d'] = []
graph['b'] = ['t', 1]
graph['t'] = []
graph['c'] = ['e', 1]
graph['e'] = []
graph[1] = []


def bfs(name):
    search_queue = graph[name]
    searched = []
    while search_queue:
        for i in range(len(search_queue)-1):
            if not search_queue[i] in searched:
                if search_queue[i] == 1:
                    print('i find f')
                else:
                    search_queue.pop(i)
                    searched.append(search_queue[i])
                    search_queue += graph[search_queue[i]]
            else:
                search_queue.pop(i)


bfs('wt')

tips:值得注意的是要考虑一种情况，就是当多个元素只想同一个元素的时候，会做无用功，所以会先考虑该元素是否已经检查过了，如果已经检查过了，就不需要再查一次，节省计算机资源。