广度优先遍历-BFS、深度优先遍历-DFS

时间：2022-03-03 21:22:02

广度优先遍历-BFS

广度优先遍历类似与二叉树的层序遍历算法，它的基本思想是：首先访问起始顶点v，接着由v出发，依次访问v的各个未访问的顶点w1 w2 w3....wn，然后再依次访问w1 w2 w3....wn的所有未被访问的邻接顶点；再从这些访问过的顶点出发，再访问它们所有未被访问过的邻接顶点......依次类推，直到图中的所有点都被访问为止。类似的思想还将应用于Dijkstra单源最短路径算法和Prim最小生成树算法。

python实现二叉树的建立以及遍历（递归前序、中序、后序遍历，队栈前序、中序、后序、层次遍历）中的树的层序遍历就用到了BFS的思想

深度优先遍历-DFS

与广度优先遍历不同，深度优先遍历类似于树的先序遍历，正如其名称中所暗含的意思一样，这种搜索算法所遵循的策略是尽可能“深”地搜索一下图。它的基本思想如下：首先访问图中某一点顶点v，然后从v出发，访问与v相邻的点w1，再从w1出发访问w1的邻接点w2....重复上述过程，直到不能继续访问时，依次退回到最近的访问点，若还有未访问的邻接点，从该节点出发，继续上面的访问过程。

下面以一个例题来展示BFS和DFS：

题目描述(2018春招-今日头条笔试题-第二题)

定义两个字符串变量：s和m，再定义两个操作：

第一种操作：m=s         s=s+s

第二种操作：s=s+m

假设s和m，初始如下：

s='a'         m=s

求最小步骤数，可以将s拼接到长度等于n

输入描述

一个整数n，表明我们需要得到s字符串长度，0<n<1000

输出描述

一个整数，表明总共操作次数

输入样例：

输入

6

输出

3

说明：

输入是6，表明我们需要得到s字符串长度为6，也就是s为最终为‘aaaaaa’,那么依次使用2次“第一种操作”和1次“第二种操作”就能达到目的，总共操作次数是3

输入

5

输出

4

说明：

输入是5，表明我们需要得到s字符串长度为5，也就是‘aaaaa’，那么直接使用4次“第二种操作”就能达到目的，总共操作次数是4

BFS

#-*- coding:utf-8 -*-

import datetime

class BFS(object):

    def __init__(self):

        self.num = 0

    def fun(self,s,m,n):

        stack=[[s,m]]

        stack_s =set()#用来存储字符串s的长度

        while True:

            if n in stack_s:

                break

            stack_temp=[]

            while stack:

                temp=stack.pop()

                temp_1=[2*temp[0],temp[0]]

                temp_2=[temp[0]+temp[1],temp[1]]

                stack_s.add(2 * temp[0])

                stack_s.add(temp[0]+temp[1])

                stack_temp.append(temp_1)

                stack_temp.append(temp_2)

            self.num+=1

            stack=stack_temp

if __name__=='__main__':

    n = input()

    i = datetime.datetime.now()

    bfs = BFS()

    bfs.fun(1, 1,n)

    j = datetime.datetime.now()

    print bfs.num

    print j - i

输入：

10000

输出：

20
0:00:02.296000

DFS：

#-*- coding:utf-8 -*-

import datetime

class DFS(object):

    '''

        num:用于存储最后执行次数

        n:用于存储最后达到的字符串的长度

        flag:当达到输入字符串的长度时，flag置为1

    '''

    def __init__(self,n):

        self.num=0

        self.n=n

        self.flag=0

    def fun(self,s,m):

        self.fun_1(s,m)

        self.fun_2(s,m)

        #当未达到字符串长度时，回溯

        if self.flag==0:

            self.num-=1

    #fun_1:方法1

    def fun_1(self,s,m):

        #当达到字符串长度，直接返回

        if self.flag == 0:

            if self.n < s:

                return

            if self.n == s:

                self.flag = 1

                return

            else:

                m = s

                s += s

                self.num += 1

            #没达到字符串长度，继续递归

            self.fun(s, m)

        else:

            return

    # fun_2:方法2

    def fun_2(self,s,m):

        if self.flag == 0:

            if self.n<s:

                return

            if self.n==s:

                self.flag=1

                return

            else:

                s=s+m

                self.num+=1

            # 没达到字符串长度，继续递归

            self.fun(s,m)

        else:

            return

if __name__=='__main__':

    n=input()

    i=datetime.datetime.now()

    dfs=DFS(n)

    dfs.fun(1,1)

    j = datetime.datetime.now()

    print dfs.num

    print j-i

输入：

10000

输出：

20
0:00:00.034000

相关文章