| BFS | 您所在的位置：网站首页 › 图的遍历实验原理 › BFS |
BFS
|
宽度优先搜索BFS ~工作方式： 从根节点开始，由里向外，逐层遍历所有节点——它每次总是扩展深度最浅的节点。 ~缺点：在树的层次较深&子节点数较多的情况下，消耗内存十分严重。 ~适用情况：节点的子节点数量不多，并且树的层次不会太深的情况。 ~简单举例：BFS方法，从根节点1开始，下图遍历顺序是：1，2，3，4，5，6 图可以采用二维数组或者邻接表来保存 下面，我将用图来展示BFS算法的工作过程： 以下用两种方式实现BFS算法： 1.队列的方式 # -*- coding: utf-8 -*- #BFS算法的队列实现 from Queue import Queue from Stack import Stack from simplegraph import * def BFS(G,v,goal,came_from):#G为导入的图；v为起始节点；goal为目标节点； frontier=Queue() frontier.enqueue(v) came_from[v]=None visited={} while not frontier.is_empty():#队列不为空 v=frontier.dequeue()#将节点v取出队列 if visited.get(v)==None:#判断节点v是否被访问过 if v==goal: return v else: visited[v]=True#节点v被访问 for w in G.adjacentEdges(v):#依次取节点v的相邻节点w frontier.enqueue(w)#将v相邻节点放入队列 came_from[w]=v return None def main(): came_from = {} start = '1' goal = '12' found = BFS(G1,start,goal,came_from) print('start:',start) print('goal:',goal) if found != None: s = Stack() s.push(found) found = came_from.get(found) while found != None: s.push(found) found = came_from.get(found) while not s.is_empty(): print(s.pop(),end='-') print('end') else: print('Path not found!') if __name__ == '__main__': main() # -*- coding: utf-8 -*- #Stack类,Stack类实现简单的栈 class Stack: def __init__(self): self.items = [] def push(self,item): self.items.append(item) def pop(self): return self.items.pop() def is_empty(self): return self.items == [] def peek(self): return self.items[-1] def top(self): return self.items[-1] def size(self): return len(self.items) def main(): s = Stack() print(s.is_empty()) s.push(1) s.push(2) s.push(3) s.push(4) print(s.size()) print(s.top()) print(s.is_empty()) while not s.is_empty(): print(s.pop()) if __name__ == '__main__': main() class SimpleGraph: def __init__(self): self.edge = {} def adjacentEdges(self,v): return self.edges[v] G1 = SimpleGraph() G1.edges = { '1' : ['2','3','4'], '2' : ['5','6'], '3' : [], '4' : ['7','8'], '5' : ['9','10'], '6' : [], '7' : ['11','12'], '8' : [], '9' : [], '10': [], '11': [], '12': [] } # -*- coding: utf-8 -*- class Queue: def __init__(self): self.items=[] def enqueue(self,item): self.items.insert(0,item) def dequeue(self): return self.items.pop() def is_empty(self): return self.items == [] def size(self): return len(self.items) def main(): q = Queue() q.enqueue(1) q.enqueue(2) q.enqueue(3) q.enqueue(4) q.enqueue(5) print(q.size()) while not q.is_empty(): print(q.dequeue()) print(q.size()) if __name__ == '__main__': main()2.BFS算法的OPEN-CLOSED实现 # -*- coding: utf-8 -*- #BFS算法的OPEN-CLOSED实现 from Stack import Stack from simplegraph import * def BFS(G,v,goal,came_from): open = [v] closed = [] came_from[v] = None while len(open) != 0: v = open.pop(0) if v == goal: return v else: closed.append(v) for w in G.adjacentEdges(v): if w not in closed: open.append(w) came_from[w] = v return None def main(): came_from = {} start = '1' goal = '12' found = BFS(G1,start,goal,came_from) print('start:',start) print('goal:',goal) if found != None: s = Stack() s.push(found) found = came_from.get(found) while found != None: s.push(found) found = came_from.get(found) while not s.is_empty(): print(s.pop(),end = '-') print('end') else: print('Path not found!') if __name__ == '__main__': main()代码中的图如下： |
优先访问深度最浅的节点，故，老节点总是优先于新节点被访问，因此，我们可以使用队列来管理节点。 BFS算法的工作原理如下： 1.将根节点放入队列 2.重复以下，直到队列为空 { 2.1 取出队列头的点 2.2 找出与该点相邻并没有被访问的节点，标记后依次放入队列 }
1.将起始节点1放入队列，进行标记 
2.从队列取出头节点1，找到与该节点邻接的节点，依次放入队列，标记为已访问 
3.取出队列头节点2，找到与2节点邻接的节点1，5，6。节点1已被访问，将节点5，6依次放入队列，标记为已访问 
直到队列为空，后面操作重复，不再赘述。
【本文地址】
公司简介
联系我们