首页> 软件工程> python实现BFS和DFS算法

[文章]python实现BFS和DFS算法

收藏
0 499 0

【摘要】

       图表示的是多点之间的连接关系,由节点和边组成。类型分为有向图,无向图,加权图等,任何问题只要能抽象为图,那么就可以应用相应的图算法。在有向图和无向图中,如果节点之间无权值或者权值相等,那么dfsbfs时常出现在日常算法中。不仅如此,dfsbfs不仅仅能够解决图论的问题,在其他问题的搜索上也是最基础(但是策略不同)两种经典算法并且五大经典算法的回溯算法其实也是dfs的一种。dfs,bfs基础能够解决搜索类问题的大部分情况,只不过搜索随着数据增大而呈非线性的增长,所以两种算法在数据较多的情况是不太适用的。

 

【正文】

以有向图举例,有向图的邻居节点是要顺着箭头方向,逆箭头方向的节点不算作邻居节点。python中,我们使用字典来表示图,我们将图相邻节点之间的连接转换为字典键值之间的映射关系。

一、      广度优先搜索(BFS

概念: BFS,其英文全称是Breadth First Search BFS并不使用经验法则算法。从算法的观点,所有因为展开节点而得到的子节点都会被加进一个先进先出的队列中。一般的实验里,其邻居节点尚未被检验过的节点会被放置在一个被称为 open 的容器中(例如队列或是链表),而被检验过的节点则被放置在被称为 closed 的容器中。(open-closed表)。

广度优先搜索的适用场景:只适用于深度不深且权值相同的图,搜索的结果为最短路径或者最小权值和。

 

代码实现:

#!/usr/bin/python
# -*- coding: utf-8 -*-

from collections import deque
from collections import namedtuple


def bfs(start_node, end_node, graph):  # 开始节点  目标节点 图字典
   
node = namedtuple('node', 'name, from_node')    # 使用namedtuple定义节点,用于存储前置节点
   
search_queue = deque()  # 使用双端队列,这里当作队列使用,根据先进先出获取下一个遍历的节点
   
name_search = deque()   # 存储队列中已有的节点名称
   
visited = {}            # 存储已经访问过的节点

   
search_queue.append(node(start_node, None))  # 填入初始节点,从队列后面加入
   
name_search.append(start_node)               # 填入初始节点名称
   
path = []               # 用户回溯路径
   
path_len = 0            # 路径长度

   
print(u'开始搜索...')
   
while search_queue:     # 只要搜索队列中有数据就一直遍历下去
       
print(u'待遍历节点: ', name_search)
        current_node
= search_queue.popleft()  # 从队列前边获取节点,即先进先出,这是BFS的核心
       
name_search.popleft()                  # 将名称也相应弹出
       
if current_node.name not in visited:   # 当前节点是否被访问过
           
print(u'当前节点: ', current_node.name)
           
if current_node.name == end_node:  # 退出条件,找到了目标节点,接下来执行路径回溯和长度计算
               
pre_node = current_node        # 路径回溯的关键在于每个节点中存储的前置节点
               
while True:                    # 开启循环直到找到开始节点
                   
if pre_node.name == start_node:  # 退出条件:前置节点为开始节点
                       
path.append(start_node)      # 退出前将开始节点也加入路径,保证路径的完整性
                       
break
                    else
:
                       
path.append(pre_node.name)   # 不断将前置节点名称加入路径
                       
pre_node = visited[pre_node.from_node]  # 取出前置节点的前置节点,依次类推
               
path_len = len(path) - 1       # 获得完整路径后,长度即为节点个数-1
               
break
            else
:
               
visited[current_node.name] = current_node   # 如果没有找到目标节点,将节点设为已访问,并将相邻节点加入搜索队列,继续找下去
               
for node_name in graph[current_node.name]:  # 遍历相邻节点,判断相邻节点是否已经在搜索队列
                    
if node_name not in name_search:        # 如果相邻节点不在搜索队列则进行添加
                       
search_queue.append(node(node_name, current_node.name))
                        name_search.
append(node_name)
   
print(u'搜索完毕,最短路径为:', path[::-1], u"长度为:", path_len)  # 打印搜索结果


if __name__ == "__main__":

   
graph = dict()      # 使用字典表示有向图
   
graph[1] = [3, 2]
    graph[
2] = [5]
    graph[
3] = [4, 7]
    graph[
4] = [6]
    graph[
5] = [6]
    graph[
6] = [8]
    graph[
7] = [8]
    graph[
8] = []
   
bfs(1, 8, graph)    # 执行搜索

 

 

二、      深度优先搜索(DFS

概念:深度优先搜索属于图算法的一种,英文缩写为DFSDepth First Search。其过程简要来说是对每一个可能的分支路径深入到不能再深入为止,而且每个节点只能访问一次。      

pythondeque根据pop还是popleft可以当成栈或队列使用,DFS的能够很快给出解,但不一定是最优解。深度优先搜索的适用场景: 针对深度很深或者深度不确定的图或者权值不相同的图可以适用DFS,优势在于节省资源,但想要得到最优解需要完整遍历后比对所有路径选取最优解。

 

代码实现:

#!/usr/bin/python
# -*- coding: utf-8 -*-

from collections import deque
from collections import namedtuple


def dfs(start_node, end_node, graph):
   
node = namedtuple('node', 'name, from_node')
    search_stack
= deque()  # 这里当作栈使用
   
name_search = deque()
    visited
= {}

    search_stack.
append(node(start_node, None))
    name_search.
append(start_node)
    path
= []
    path_len
= 0

   
print(u'开始搜索...')
   
while search_stack:
       
print(u'待遍历节点: ', name_search)
        current_node
= search_stack.pop()  # 使用栈模式,即后进先出,这是DFS的核心
       
name_search.pop()
       
if current_node.name not in visited:
           
print(u'当前节点: ', current_node.name)
           
if current_node.name == end_node:
               
pre_node = current_node
               
while True:
                   
if pre_node.name == start_node:
                       
path.append(start_node)
                       
break
                    else
:
                       
path.append(pre_node.name)
                        pre_node
= visited[pre_node.from_node]
                path_len
= len(path) - 1
               
break
            else
:
               
visited[current_node.name] = current_node
               
for node_name in graph[current_node.name]:
                   
if node_name not in name_search:
                       
search_stack.append(node(node_name, current_node.name))
                        name_search.
append(node_name)
   
print(u'搜索完毕,路径为:', path[::-1], u"长度为:", path_len)  # 这里不再是最短路径,深度优先搜索无法一次给出最短路径


if __name__ == "__main__":

   
graph = dict()
    graph[
1] = [3, 2]
    graph[
2] = [5]
    graph[
3] = [4, 7]
    graph[
4] = [6]
    graph[
5] = [6]
    graph[
6] = [8]
    graph[
7] = [8]
    graph[
8] = []
   
dfs(1, 8, graph)

 

软件工程
最近热帖
{{item.Title}} {{item.ViewCount}}
近期热议
{{item.Title}} {{item.PostCount}}