DFS vs BSF

DFS(深度优先搜索=Depth-First Search)

BFS(广度优先搜索=Breadth-First Search)

用于对图(树)进行遍历搜索的两种经典方法。

一、DFS

深度优先搜索,从起点出发,从规定的方向中选择其中一个不断地向前走,直到无法继续为止,然后尝试另外一种方向,直到最后走到终点。就像走迷宫一样,尽量往深处走。

解决什么问题?答:连通性的问题

用什么数据结构?答:  stack

核心代码:

def dfs(adj, start):
    visited = set()
    stack = [[start, 0]]
    while stack:
        (v, next_child_idx) = stack[-1]
        if (v not in adj) or (next_child_idx >= len(adj[v])):
            stack.pop()
            continue
        next_child = adj[v][next_child_idx]
        stack[-1][1] += 1
        if next_child in visited:
            continue
        print(next_child)
        visited.add(next_child)
        stack.append([next_child, 0])



二、BFS

广度优先的搜索是从起始点出发,一层一层地进行,每层当中的点距离起始点的步数都是相同的,当找到了目的地之后就可以立即结束。

解决什么问题?答:最短路径问题

用什么数据结构?答:队列 queue。

经典应用:广度优先的搜索可以同时从起始点和终点开始进行,称之为双端 BFS。这种算法往往可以大大地提高搜索的效率。
举例:在社交应用程序中,两个人之间需要经过多少个朋友的介绍才能互相认识对方。

核心代码:

import queue
def bfs(adj, start):
    visited = set()
    q = queue.Queue()
    q.put(start)
    while not q.empty():
        u = q.get()
        print(u)
        for v in adj.get(u, []):
            if v not in visited:
                visited.add(v)
                q.put(v)

 

【经典迷宫问题】

如上图,-1表示墙体,0表示通道

问题一:A是否能到达B?

问题二:A到达B的最短路径及步数?

问题三,至多能打破k堵墙,最短路径及步数?

答:

1.使用DFS(看连通性),return true

2.利用DFS和BFS均可实现,优先推荐使用BFS,边走边记录步数即可。  时间复杂度为O(n2)

3.问题3的解决思路:想像成k+1人同时去进行BFS,将2维平面展成3维立面。

就是在原问题上改进2个点:

1.改成三维矩阵

2.向4个方向去的时候额外判断是否可以拆墙。


def mybfs(arr,start):
    xd = [1,-1,0,0]
    yd = [0, 0, 1, -1]
    visited = []
    visited.append(start)
    q = queue.Queue()
    q.put(start)
    #只要队列不为空就一直循环下去
    while not q.empty():
        u = q.get()
        #从四个方向进行BFS
        for i in range(4):
            next = [u[0]+xd[i], u[1]+yd[i]]
            xn = u[0]+xd[i]
            yn = u[1]+yd[i]
            if issafe(arr,xn,yn) and next not in visited:
                visited.append(next)
                q.put(next)
                arr[xn][yn]=arr[u[0]][u[1]]+1

 

 

 

2

发表评论

电子邮件地址不会被公开。 必填项已用*标注

微信扫一扫

微信扫一扫

微信扫一扫,分享到朋友圈

DFS vs BSF
嘿!有什么能帮到您的吗?
返回顶部

显示

忘记密码?

显示

显示

获取验证码

Close