BFS模板

图片说明

构件图的方法有两种
1.用各个节点之间的边表示(邻接矩阵）
如 edges[[0,1],[0,2],[1,4],[2,3],[2,4]]
2. 用节点之间的连接表示（邻接表）
如 [[1,2],
[0,4],
[0,3],
[2],
[1,2]]
第一行代表节点0与1，2相连，以此类推。

以第二种建图

    def initial_graph(n, edges):
        dict_graph = {}
        # 初始化邻接表
        for i in range(n):
            dict_graph[i] = []

        num_e = len(edges)
        for i in range(num_e):
            u = edges[i][0]
            v = edges[i][1]
            dict_graph[u].append(v)
            dict_graph[v].append(u)

        return dict_graph

队列

# 1.使用queue
from queue import Queue
q = Queue() # 定义，为什么是这样涉及python的设计，不是很懂
q.put(node) # 放入
q.get() # 出队
# 2.使用deque
import collections
q = collections.deque() # 双向队列
q.append() # 入队
q.popleft() # 出队

节点入队

# 使用Queue()定义
q.put(start_node)
# 为防止无向图中回溯，使用set阻断
hash_set = set()
hash_set.add(start_node)

BFS背诵部分（注重理解）

step = 0
while not q.empty():
    size = len(q)
    step += 1
    for iter_num in range(size):
        node = q.get() # 节点出队
        # get the neighbor
        for neighbor in dict_graph[node]:
            if neighbor == end_node: # 找到返回层数
                return step
            if neighbor in hash_set:# 利用set（）判断有没有访问过
                continue 
            hast_set.add(node)
            q.put(neighbor)
    return 0 # 找不到

小结

BFS不难，难在思考用不用它和一些使用时的实现细节：

BFS的终止条件，一些题目可能不是找到某一终点，而是将图中的某种元素清除。如僵尸吃人的问题，需要将人全部变成僵尸。
入队的表示元素可以将（node,step）入队，出队时拆包，从而少些一层循环，进行一定程度上加速。如 wordladder的问题，case给定wordList其实很长。

DFS模板

DFS思路是一条路走到底，撞了墙回头
以找到数组的所有子集为列，对DFS的过程进行描述

数组的子集

已知数组num[1,2,3]，要求出它的所有子集
图片说明

dfs函数定义

因为dfs涉及到程序的递归调用，一般dfs不嵌入到程序内部过程。
在主函数中，dfs作为辅助函数调用

#python中，一般定义如下：
def dfsHelper(self，
          input parameter...,
          startIndex,
          tmp,
          result):
"""
其中:
input parameter一般指不变的已知量：比如数组num，在矩阵的搜索中指矩阵grid，在图中指图graph和目标节点end_node；
startIndex用来标记当前指针在数组（矩阵或者图中的位置），随着递归而改变；
tmp:用来暂存递归过程中的结构，随着递归而改变；
result:一般为全局变量，用来保存所有的结果。
在程序撰写中，可以定义很多经常使用的量为常量，从而使dfsHelper函数更加短小精悍。
"""

DFS递归过程

递归的过程就是先在tmp中加入当前元素，然后调用自身（这中间指针后移），最后在tmp中移除当前元素。

for i in range(startIndex, len(nums)):
    tmp.append(nums[i])
    self.dfsHelper(nums, i + 1, tmp, result)
    tmp.pop()

DFS的出口

如数组边界，或visited以访问过

完整DFS

DFS求解问题的解法

class Solution:
    """
    @param nums: A set of numbers
    @return: A list of lists
    """
    def subsets(self, nums):
        # 从空集开始搜索，每次将nums的节点加入空集中
        result = []
        tmp = []

        if nums is None:
            return None

        nums.sort()

        startIndex = 0
        self.dfsHelper(nums, startIndex, tmp, result)

        return result

    def dfsHelper(self, nums, startIndex, tmp, result):
        # dfs出口
        tmp_copy = tmp.copy() # 拷贝一份
        result.append(tmp_copy)

        if startIndex == len(nums):
            return

        for i in range(startIndex, len(nums)):
            tmp.append(nums[i])
            self.dfsHelper(nums, i + 1, tmp, result)
            tmp.pop()
        return

lectcode| python的DFS,BFS常用套路模板学习