深度优先算法和广度优先算法(python)

2021年9月22日 19点热度 0条评论 来源: Asimov__

深度优先算法:深度优先搜索算法(Depth-First-Search),是搜索算法的一种。是沿着树的深度遍历树的节点,尽可能深的搜索树的分支。当节点v的所有边都己被探寻过,搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点,则选择其中一个作为源节点并重复以上过程,整个进程反复进行直到所有节点都被访问为止。属于盲目搜索
实现方法:

广度优先算法:广度优先算法(Breadth-First Search),同广度优先搜索,又称作宽度优先搜索,或横向优先搜索,简称BFS,是一种图形搜索演算法。简单的说,BFS(也是一种盲目搜寻法)是从根节点开始,沿着树的宽度遍历树的节点,如果发现目标,则演算终止。广度优先搜索的实现一般采用open-closed表。目的是系统地展开并检查图中的所有节点,以找寻结果。换句话说,它并不考虑结果的可能位置,彻底地搜索整张图,直到找到结果为止。
实现方法:

算法:

深度优先:根左右遍历(递归实现)

def  depth_tree(tree_node):
    if  tree_node   is  not None:
        print(tree_node._data)
        if  tree_node._left is  not None:
            return depth_tree(tree_node._left)
        if  tree_node._right  is  not None:
            return depth_tree(tree_node._right)

广度优先:层次遍历,一层一层的遍历(队列实现)

def   level_queue(root):
    if  root  is  None:
        pass
    my_queue=[]
    node=root
    my_queue.append(node)   ##根结点入队
    while my_queue:
        node=my_queue.pop(0)  ##出队列
        print(node.elem)      ##访问结点
        if  node.lchild  is  not  None:
            my_queue.append(node.lchild)    ##入队
        if  node.rchild  is  not  None:
            my_queue.append(node.rchild)    ##入队

代码实现:

构建如上图树

一.列表法:

用列表构建如上图树:

 my_Tree = [
    'D',  ##根结点
    ['B',
     ['F', [], []],
     ['G', ['E', [], []], []]
     ],  ##左子叶
    ['C',[],
     ['A', ['H', [], []], []]
     ]  ##右子叶
]

深度优先

print(my_Tree[1])
print(my_Tree[2])

def depth_tree(tree_node):
    if tree_node:
        print(tree_node[0])
        ##访问左子叶
        if tree_node[1]:

            depth_tree(tree_node[1])  ##递归遍历
        # ##访问右子叶
        if tree_node[2]:

            depth_tree(tree_node[2])  ##递归遍历

depth_tree(my_Tree)

#D B F G E C A H

广度优先:

def   level_queue(root):
    if  not  root:
        pass
    my_queue=[]
    node=root
    my_queue.append(node)   ##根结点入队
    while my_queue:
        node=my_queue.pop(0)  ##出队列
        print(node[0])      ##访问结点
        if  node[1]:
            my_queue.append(node[1])    ##入队
        if  node[2]:
            my_queue.append(node[2])    ##入队
level_queue(my_Tree)

#D B F G E C A H

二.构造类结点法:

class  Tree:
    root=''
    right=None
    left=None
    ##初始化类
    def __init__(self,node):
        self.root=node
    def set_root(self,node):
        self.root=node
    def get_root(self,node):
        return self.root
##初始化树
a=Tree('A')
b=Tree('B')
c=Tree('C')
d=Tree('D')
e=Tree('E')
f=Tree('F')
g=Tree('G')
h=Tree('H')

##根据点的联系,生成关系树
a.left=h
b.left=f
b.right=g
c.right=a
d.left=b
d.right=c
g.left=e

深度优先:

def depth_tree(tree_node):
    if tree_node is not None:
        print(tree_node.root)
        if tree_node.left is not None:
             depth_tree(tree_node.left)      ##递归遍历
        if tree_node.right is not None:
             depth_tree(tree_node.right)
##传入根结点
depth_tree(d)


#D B F G E C A H

广度优先:

def   level_queue(root):
    if  root  is  None:
        pass
    my_queue=[]
    node=root
    my_queue.append(node)   ##根结点入队
    while my_queue:
        node=my_queue.pop(0)  ##出队列
        print(node.root)      ##访问结点
        if  node.left  is  not  None:
            my_queue.append(node.left)    ##入队
        if  node.right  is  not  None:
            my_queue.append(node.right)    ##入队
level_queue(d)

#D B F G E C A H

    原文作者:Asimov__
    原文地址: https://blog.csdn.net/qq_41661056/article/details/95605803
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系管理员进行删除。