算法——广搜(BFS)/深搜(DFS)

今天药忘吃喽~ 2021-11-05 07:04 439阅读 0赞

**    在图的基本算法中，最初接触的就是图的遍历算法，根据访问节点的顺序，可分为广度优先搜索（`BFS`）和深度优先搜索（`DFS`）。**

# 广度优先搜索 #

**广度优先搜索算法主要解决两个问题：**

1.  **从节点A出发有到节点B的路径吗？**
2.  **从节点A出发到节点B的最短路径是哪条？**

** 实现方式：**

**它的实现方式可以用队列的数据结构去理解（先进先出），每次取出一个节点都将这个节点相邻的节点加入队列尾部，直到找到需要寻找的节点。（这里需要注意的是循环依赖的问题，通常每取出一个节点就将其放入一个数组中，然后每次入队时都判断一下是否已使用过这个节点了）**

**实现：**

**首先我会生成一颗二叉树，然后根据广搜，一层一层的便利：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NTk4MDEx_size_16_color_FFFFFF_t_70][]

class Node(object):
        """初始化一个节点,需要为节点设置值"""
    
        def __init__(self, val):
            self.val = val
            self.left = None
            self.right = None
    
    
    class BinaryTree(object):
        """
        创建二叉树,完成
        - 添加元素
        - 广度遍历
        """
    
        def __init__(self):
            self.root = None
            pass
    
        # 添加元素
        def addNode(self, val):
            # 创建队列结构存储结点
            nodeStack = [self.root]
    
            # 如果根结点为空
            if self.root == None:
                self.root = Node(val)
                print("添加根节点{0}成功!".format(self.root.val))
                return
    
            # 模拟生成一颗二叉树，本身只持有root节点
            while len(nodeStack) > 0:
                # 队列元素出列
                p_node = nodeStack.pop()
    
                # 如果左子结点为空
                if p_node.left == None:
                    p_node.left = Node(val)
                    print("添加左:{0} ".format(p_node.left.val))
                    return
    
                # 如果右子节点为空
                if p_node.right == None:
                    p_node.right = Node(val)
                    print("添加右:{0} ".format(p_node.right.val))
                    return
    
                # 入队
                nodeStack.insert(0, p_node.left)
                nodeStack.insert(0, p_node.right)
    
        # 广度优先遍历
        def BFS(self):
            nodeStack = [self.root];
    
            # 只要队列不为空
            while len(nodeStack) > 0:
                my_node = nodeStack.pop()
                print("-->", my_node.val)
    
                if my_node.left is not None:
                    nodeStack.insert(0, my_node.left)
    
                if my_node.right is not None:
                    nodeStack.insert(0, my_node.right)
    
    
    
    def main():
        # 生成一个二叉树
        bt = BinaryTree()
        bt.addNode(0)
        bt.addNode(1)
        bt.addNode(2)
        bt.addNode(3)
        bt.addNode(4)
        bt.addNode(5)
        bt.addNode(6)
        bt.addNode(7)
        bt.addNode(8)
        bt.addNode(9)
    
        print("广度遍历-->")
        bt.BFS()
    
    
    if __name__ == '__main__':
        main()

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NTk4MDEx_size_16_color_FFFFFF_t_70 1][]

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

# 深度优先搜索 #

**深度优先搜索算法解决的问题有：**

1.  **通过便利所有节点路径找到最小权重路径**

** 实现方式：**

**它的实现方式可以用栈的数据结构去理解（先进后出），每次出栈时，都将它相邻的节点，压入栈头。直到该条路径都便利完了，它会回溯到上个节点然后继续这个步骤。（这里需要注意的是循环依赖的问题，通常每取出一个节点就将其放入一个数组中，然后每次入队时都判断一下是否已使用过这个节点了）**

**实现：**

**首先我会生成一颗二叉树，然后根据深搜，进行先序便利：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NTk4MDEx_size_16_color_FFFFFF_t_70][]

class Node(object):
        """初始化一个节点,需要为节点设置值"""
    
        def __init__(self, val):
            self.val = val
            self.left = None
            self.right = None
    
    
    class BinaryTree(object):
        """
        创建二叉树,完成
        - 添加元素
        - 深度遍历
        """
    
        def __init__(self):
            self.root = None
            pass
    
        # 添加元素
        def addNode(self, val):
            # 创建队列结构存储结点
            nodeStack = [self.root]
    
            # 如果根结点为空
            if self.root == None:
                self.root = Node(val)
                print("添加根节点{0}成功!".format(self.root.val))
                return
    
            # 模拟生成一颗二叉树，本身只持有root节点
            while len(nodeStack) > 0:
                # 队列元素出列
                p_node = nodeStack.pop()
    
                # 如果左子结点为空
                if p_node.left == None:
                    p_node.left = Node(val)
                    print("添加左:{0} ".format(p_node.left.val))
                    return
    
                # 如果右子节点为空
                if p_node.right == None:
                    p_node.right = Node(val)
                    print("添加右:{0} ".format(p_node.right.val))
                    return
    
                # 入队
                nodeStack.insert(0, p_node.left)
                nodeStack.insert(0, p_node.right)
    
    
        # 深度优先(先序遍历)栈
        def DFS(self, start_node):
    
            # 如果节点为null说明没有val
            if start_node == None:
                return
    
            print("-->", start_node.val)
            # 入栈,先入先出
            self.DFS(start_node.left)
            self.DFS(start_node.right)
    
    
    
    def main():
        # 生成一个二叉树
        bt = BinaryTree()
        bt.addNode(0)
        bt.addNode(1)
        bt.addNode(2)
        bt.addNode(3)
        bt.addNode(4)
        bt.addNode(5)
        bt.addNode(6)
        bt.addNode(7)
        bt.addNode(8)
        bt.addNode(9)
    
        print("先序遍历-->")
        bt.DFS(bt.root)
    
    
    
    if __name__ == '__main__':
        main()

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NTk4MDEx_size_16_color_FFFFFF_t_70 2][]

**结论：深度优先搜索的适用于针对深度很深或者深度不确定的图或者权值不相同的图，优势在于节省资源，但想要得到最优解需要完整遍历后比对所有路径选取最优解。**

**例子：**

**通过广搜和深搜便利文件目录：**

**广搜：**

import os
    import collections
    
    # if __name__ == '__main__':
    # main()
    
    def getAllDirByBFS(path):
        queue = collections.deque()
        # 进队
        queue.append(path)
        # 循环，当队列为空，停止循环
        while len(queue) > 0:
            # 出队数据 这里相当于找到A元素的绝对路径
            dirPath = queue.popleft()
            try:
                # 找出跟目录下的所有的子目录信息，或者是跟目录下的文件信息
                dirList = os.listdir(dirPath)
                # 遍历该文件夹下的其他信息
                for filename in dirList:
                    # 绝对路径
                    dirAbsPath = os.path.join(dirPath, filename)
                    # 判断：如果是目录dir入队操作，如果不是dir打印出即可
                    if os.path.isdir(dirAbsPath):
                        print("目录：" + dirAbsPath + filename)
                        queue.append(dirAbsPath)
                    else:
                        print("普通文件：" + dirAbsPath + filename)
            except:
                print("打开异常" + dirPath)
    
    
    # 函数的调用
    getAllDirByBFS('D:\\automatedTestTool')

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NTk4MDEx_size_16_color_FFFFFF_t_70 3][]

**深搜：**

import os
    
    
    def getAllDirByDFS(path):
        stack = []
        # 压栈操作,相当于图中的A压入
        stack.append(path)
        # 处理栈，当栈为空的时候结束循环
        while len(stack) > 0:
            # 从栈里取数据，相当于取出A，取出A的同时把BC压入
            dirPath = stack.pop()
            try:
                firstList = os.listdir(dirPath)
                # 判断：是目录压栈，把该目录地址压栈，不是目录即是普通文件，打印
                for filename in firstList:
                    fileAbsPath = os.path.join(dirPath, filename)
                    if os.path.isdir(fileAbsPath):
                        # 是目录就压栈
                        stack.append(fileAbsPath)
                        getAllDirByDFS(fileAbsPath)
                    else:
                        # 是普通文件就打印即可，不压栈
                        print("普通文件：", fileAbsPath + filename)
            except:
                print("打开异常" + dirPath)
    
    
    getAllDirByDFS(r'D:\\automatedTestTool')

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NTk4MDEx_size_16_color_FFFFFF_t_70 4][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NTk4MDEx_size_16_color_FFFFFF_t_70]: /images/20211104/6fdef04270f24e58ada4504db8f9f819.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NTk4MDEx_size_16_color_FFFFFF_t_70 1]: /images/20211104/4df5fb5059ed4325812b920914ed4691.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NTk4MDEx_size_16_color_FFFFFF_t_70 2]: /images/20211104/6f898f937dcb472aa07605eb9ec2b8f3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NTk4MDEx_size_16_color_FFFFFF_t_70 3]: /images/20211104/dc38b8de2f97477ab8ee19d6e575733b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NTk4MDEx_size_16_color_FFFFFF_t_70 4]: /images/20211104/af4447ed3bd64ffa8a5c99d4009c5d25.png