2020-03-21 11:23 已编辑武汉理工大学测试开发

关注

深度优先搜索算法例题

1. 问题和资源

1.1. 深度优先搜索的伪代码

递归

    基本思想：　
    递归实现：
                 （1）访问顶点v，修改顶点状态
                 （2）遍历v的子节点w，while（w存在），递归执行该节点；

    代码：
      /布尔型数组Visited[]初始化成false
      void DFS(Vetex v)
      {
          Visited[v] = true;
          for each w adjacent to v     # 遍历顶点v的邻接顶点
              if (!Visited[w])        # 如果没有访问过，就以改点为顶点，接着访问
                  DFS(w);
      }

非递归
可以参考这里 https://www.cnblogs.com/gczr/p/6476577.html
暂时不要求掌握

参考 https://blog.csdn.net/u011095253/article/details/9158387

1.2. 针对一个深度优先搜索的题目，应该如何分析

如果需要查找所有的结果

定义res保存所有结果；
DFS中增加tmp保存临时结果；
思考“层数”的含义（下例子中的pos）
符合条件的时候将tmp添加到res中
退到上一层循环的时候修改元素状态。

简化

定义全局的存放所有解的对象和存放一个对象的解。
在递归函数中，确定递归的终止条件，并在终止的时候提交一个完整的解。
递归函数中的结构是：执行动作、调用递归、撤销动作

需要考虑

递归终止条件
递归传递的参数（一般情况下可以为pos,tmp;但是有时候需要适当地改变）

一个经典的题目是“全排列”

2. 经典题目-生成数字集合

2.1. 子集

def subsets(nums):
    nums.sort()
    res = [[]]   # 存储所有的结果
    n = len(nums)

    # 临时变量，满足一定条件的时候就添加到res中
    # pos表示起点位置，在这里用来表示子集的起点，从而保证不会重复
    def DFS(pos, tmp):   
        for i in range(pos,n):
            tmp.append(nums[i])
            res.append(tmp[:])      # 将符合条件的元素添加到res中，因为这里只要是子集都符合，所以直接添加，不需要判断条件。

#             print("i=",i,"tmp=",tmp,"res=",res)
            DFS(i+1, tmp)    # 以当前位置向下递归一层。
            tmp.pop()# 递归结束之后，重新修改tmp中的元素，也就是修改元素状态。这里的删除元素也就是表示将这个元素的访问状态重置为没有访问


    DFS(0,[])
    return res

nums = [1,2,3]
subsets(nums)

[[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]]

2.2. 子集II

leetcode

使用第一个思路就可以了，之后去除掉重复元素就ok了。

def subsetsWithDup(nums):
    nums.sort()
    res = [[]]   # 存储所有的结果
    n = len(nums)

    # 临时变量，满足一定条件的时候就添加到res中
    # pos表示起点位置，在这里用来表示子集的起点，从而保证不会重复
    def DFS(pos, tmp):   
        for i in range(pos,n):
            tmp.append(nums[i])
            if tmp[:] not in res:
                res.append(tmp[:])      # 将符合条件的元素添加到res中，因为这里只要是子集都符合，所以直接添加，不需要判断条件。

#             print("i=",i,"tmp=",tmp,"res=",res)
            DFS(i+1, tmp)    # 以当前位置向下递归一层。
            tmp.pop()# 递归结束之后，重新修改tmp中的元素，也就是修改元素状态。这里的删除元素也就是表示将这个元素的访问状态重置为没有访问


    DFS(0,[])
    return res

nums = [1,2,2]
subsetsWithDup(nums)

[[], [1], [1, 2], [1, 2, 2], [2], [2, 2]]

3. 全排列

leetcode
参考

"""
1. 定义全局变量保存所有结果。定义临时变量存储一个解对象
2. 定义递归截止的条件，这里也就是凑齐3个数的时候。
3. 递归过程中的代码结构是：执行动作、调用递归、撤销动作
"""
def permute(nums):
    res = []
    state = [0 for _ in range(len(nums))]

    def DFS(pos, tmp):
        if pos == len(nums):   # 递归的一个终止条件，此时得到一个解
            res.append(tmp[:])
            return   # 得到一个解，此时就需要返回

        for i in range(len(nums)):
            if state[i] == 0:
                # 执行动作
                state[i] = 1
                tmp.append(nums[i])

                # 调用递归
                DFS(pos+1, tmp)

                # 撤销动作
                tmp.pop()
                state[i] = 0

    DFS(0, [])
    return res

nums = [1,2,3]
permute(nums)

[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

4. 全排列II

leetcode

"""
思路和全排列一样，不过增加一个判断条件即可。
"""
"""
1. 定义全局变量保存所有结果。定义临时变量存储一个解对象
2. 定义递归截止的条件，这里也就是凑齐3个数的时候。
3. 递归过程中的代码结构是：执行动作、调用递归、撤销动作
"""
def permute(nums):
    res = []
    state = [0 for _ in range(len(nums))]

    def DFS(pos, tmp):
        if pos == len(nums):   # 递归的一个终止条件，此时得到一个解
            if tmp[:] not in res:
                res.append(tmp[:])
            return   # 得到一个解，此时就需要返回

        for i in range(len(nums)):
            if state[i] == 0:
                # 执行动作
                state[i] = 1
                tmp.append(nums[i])

                # 调用递归
                DFS(pos+1, tmp)

                # 撤销动作
                tmp.pop()
                state[i] = 0

    DFS(0, [])
    return res

nums = [1,1,2]
permute(nums)

[[1, 1, 2], [1, 2, 1], [2, 1, 1]]

5. 组合总合

"""
1. 通过读题可以了解到需要获取所有的解，所以考虑是否可以采用深度优先搜索。
2. 递归终止条件（什么时候返回）是：这里采用不断地向tmp中增加，当大于等于target的时候就返回，表示需要进行pop。
3. 因为元素可以重复使用，因此每次的for循环都是从0开始，而不需要像“子集”这个题中只可以大于当前位置的地方取值。
"""
def combinationSum(candidates, target):
    candidates.sort()

    res = []
    n = len(candidates)

    def helper(tmp):
        if sum(tmp) >= target:
            if sum(tmp) == target:
                res.append(tmp[:])
            return            

        for i in range(n):    # 注意这里
            tmp.append(candidates[i])
            helper(tmp)
            tmp.pop()

    helper([])

    new_res = []
    # 存在重复的组合，需要进行过滤
    for item in res:
        item.sort()
        if item not in new_res:
            new_res.append(item)
    return new_res

candidates = [1,2]
target=4

combinationSum(candidates, target)

[[1, 1, 1, 1], [1, 1, 2], [2, 2]]

这种题还有另外的解决办法，就是使用hash表来解决。

6. 组合综合II

"""
相对于组合总和I，现在每个元素的使用次数被限制了为1次，因此需要设置一个参数用于保存每个元素被访问的次数。
"""
"""
1. 通过读题可以了解到需要获取所有的解，所以考虑是否可以采用深度优先搜索。
2. 递归终止条件（什么时候返回）是：这里采用不断地向tmp中增加，当大于等于target的时候就返回，表示需要进行pop。
3. 因为元素可以重复使用，因此每次的for循环都是从0开始，而不需要像“子集”这个题中只可以大于当前位置的地方取值。
"""
def combinationSum(candidates, target):
    candidates.sort()

    res = []
    n = len(candidates)
    count = [0 for item in range(n)]

    def helper(tmp):
        if sum(tmp) >= target:
            a = tmp[:]
            a.sort()
            if sum(a) == target and a not in res:
                res.append(a)
            return            

        for i in range(n):    # 注意这里
            if count[i] == 0:
                count[i] += 1
                tmp.append(candidates[i])
                helper(tmp)
                tmp.pop()
                count[i] -= 1

    helper([])
    return res

candidates = [1,2,3,2,3,4]
target=6

combinationSum(candidates, target)

[[1, 2, 3], [2, 4], [3, 3]]
[[1, 2, 3], [2, 4], [3, 3]]

上面的代码执行的时候会超出时间限制，另一种思路是使用词典的方法来解决。

7. 生成括号-可以参考解题思路

"""
主要思路是一样的，关键是要插入右括号的时候前面存在一个左括号。
"""
def generateParenthesis(n):
    res = []
    parenthesis = {
        "(":0,
        ")":0
    }

    def helper(tmp):
        # 递归终止条件就是临时数组中的个数达到指定长度
        if len(tmp) == 2*n:
            res.append("".join(tmp[:]))

        # 遍历的元素是tmp中可以使用的元素。比如全排列的时候，可以使用的是1,2,3，所以便利的是range(1,4)
        for i in ['(',')']:    
            parenthesis[i] += 1
            # 此时只可以插入左括号
            tmp.append(i)
            if parenthesis["("] >= parenthesis[")"] and parenthesis[i]<=n:
                helper(tmp)
            tmp.pop()
            parenthesis[i] -= 1


    helper([])
    return res

generateParenthesis(3)

['((()))', '(()())', '(())()', '()(())', '()()()']

上面采用的是限制tmp中括号的插入顺序，从而得到符合条件的括号排序，最终直接添加到res中。另一种解法是先输出括号的全排列，然后判断符合的括号排序。
上面的for循环，一般遍历的是可以使用的元素，这里也就是左括号和右括号。（这一点很重要）
状态修改和添加到tmp中是同时进行的。也就是上面的parenthesis[i] += 1;tmp.append(i)【这一点很重要】。判断语句用于判断是否符合向下递归的条件。

8. 电话号码的字母组合--解题思想是一样的。

leetcode

思路：整体思路还是一样的，只不过是每个数字对应了多个选择，需要注意的是数字状态的记录即可。

DIGITS = {
    '2':['a','b','c'],
    '3':['d','e','f'],
    '4':['g','h','i'],
}

def letterCombinations(digits):
    res = []
    state = {}  # 初始化
    for i in '23456789':
        state[i] = 0
    print(state)

    def helper(tmp):
        if len(tmp) == len(digits):
            if set(tmp) not in res:
                res.append("".join(tmp[:]))

        for st in digits:
            for j in DIGITS[st]:
                if state[st] == 0:
                    tmp.append(j)
                    state[st] = 1    # 注意
                    helper(tmp)
                    tmp.pop()
                    state[st] = 0
    helper([])
    return res

letterCombinations('23')

{'2': 0, '3': 0, '4': 0, '5': 0, '6': 0, '7': 0, '8': 0, '9': 0, '1': 1}
['ad', 'ae', 'af', 'bd', 'be', 'bf', 'cd', 'ce', 'cf']

8.1. 改进-考虑字符串的顺序

也就是，首先需要主要的是上面的23的组合输出中包含了32的组合输出，也就是没有顺序性。
一种思路就是当添加元素的时候需要判断前一个元素是否已经考虑了。此时，可以新增加一个index，用于统计对应索引元素是否已经增加到tmp中。
提交系统中出现错误，不能解决'22'这种字符串，主要是设计的时候state没有设计正确。
考虑将state和index合并起来，用于统计指定位置元素的状态。

DIGITS = {
    '2':['a','b','c'],
    '3':['d','e','f'],
    '4':['g','h','i'],
    '5':['j','k','l'],
    '6':['m','n','o'],
    '7':['p','q','r','s'],
    '8':['t','u','v'],
    '9':['w','x','y','z']
}

def letterCombinations(digits):
    if len(digits)==0:
        return []

    res = [] 
    state = [0 for item in range(len(digits))]    # *******重要*************

    def helper(tmp):
        if len(tmp) == len(digits):
            if set(tmp) not in res:
                res.append("".join(tmp[:]))

        for i in range(len(digits)):
            for j in DIGITS[digits[i]]:
                if (i == 0  or (i >= 1 and state[i-1] == 1)) and state[i] == 0:   # **********重要*************8
                    state[i] = 1
                    tmp.append(j)
                    helper(tmp)
                    tmp.pop()
                    state[i] = 0
    helper([])
    return res

letterCombinations('22')

['aa', 'ab', 'ac', 'ba', 'bb', 'bc', 'ca', 'cb', 'cc']

8.2. 值得借鉴

当考虑输出字符的顺序的时候，可以使用state来进行判断前一个字符是否输出了，如果前一个字符没有输出，那么就不输出下一个字符。上面代码中使用state来实现这一过程。

9. 复原IP地址-借鉴思路

首先，不增加限制条件看所有的可能组合，此时就是使用最基本的DFS结构就可以了。然后，增加限制条件（0-255）之间，根据限制条件增加到合适位置进行判断就可以了。
注意这是一种可以通用的思想，当一步解决不了算法的时候，就分步骤进行。

leetcode
首先我们要明确传统IP地址的规律是分4个Part，每个Part是从0-255的数字。这又是一个组合问题，因此考虑DFS。

9.1. 暴力法求解所有的组合

思路：将一个字符串切割成4个部分，输出所有的组合；然后判断每一个组合是否符合要求。

"""
思路：求所有组合的问题，考虑使用DFS方法。
注意事项：
1）需要在字符串中选择3个点，从而切成四个部分，因为每一次选择的点的范围应该是大于上一次选择的点，所以需要一个数组points保存上一次
切分点的位置。
"""

def splitStr(s):
    """将字符串切成4部分的所有组合"""
    res = []
    n = len(s)
    if n < 4:
        return 
    points = [0]

    def helper(tmp):
        if len(points) == 4:
            r = tmp[:]
            r.append(s[points[-1]:])
            res.append(r)

        for i in range(points[-1]+1,n):
            tmp.append(s[points[-1]:i])
            points.append(i)
            helper(tmp)
            tmp.pop()
            points.pop()

    helper([])

    return res

s = "12345"
splitStr(s)

9.2. DFS

"""
思路：求所有组合的问题，考虑使用DFS方法。
注意事项：
1）需要在字符串中选择3个点，从而切成四个部分，因为每一次选择的点的范围应该是大于上一次选择的点，所以需要一个数组points保存上一次
切分点的位置。
"""

def splitStr(s):
    """将字符串切成4部分的所有组合"""
    res = []
    n = len(s)
    if n < 4:
        return 
    points = [0]

    def helper(tmp):
        if len(points) == 4:
            r = tmp[:]
            if int(s[points[-1]:]) >=0 and int(s[points[-1]:])<= 255:
                r.append(s[points[-1]:])
                res.append(r)

        for i in range(points[-1]+1,n):
            temp_num = int(s[points[-1]:i])
            if temp_num >= 0 and temp_num <= 255:
                tmp.append(str(temp_num))
                points.append(i)
                helper(tmp)
                tmp.pop()
                points.pop()

    helper([])

    return res