美文网首页算法和数据结构数据结构程序员
数据结构(九):广度优先与深度优先

数据结构(九):广度优先与深度优先

作者: zhipingChen | 来源:发表于2018-10-26 16:03 被阅读3次

    广度优先搜索(breadth-first search)和深度优先搜索(depth-first search)是两种探索图/树中顶点的思路。这两种搜索方式可以用来查找图中某个指定的顶点,也可以用来对图中顶点进行遍历。

    广度优先方式

    广度优先遍历图的方式为,一次性访问当前顶点的所有未访问状态相邻顶点,并依次对每个相邻顶点执行同样处理。因为要依次对每个相邻顶点执行同样的广度优先访问操作,所以需要借助队列结构来存储当前顶点的相邻顶点。

    广度优先遍历图的方式,是以一种类似波纹扩散的方式进行的,不断放大辐射半径,进而覆盖整张图。

    实现方式
    1. 选择起始顶点放入队列,并标记为已访问;
    2. 当队列不为空时,从队列中取出顶点作为目标顶点,将目标顶点的所有相邻且未被访问过的顶点放入队列,并标记为已访问;
    3. 重复执行步骤 2。

    根据实现方式可知,广度优先遍历的形式为,选择目标顶点后,依次访问目标顶点的所有相邻顶点,再依次对每个相邻顶点,依次访问其相邻顶点,如此重复对顶点执行向外扩散的访问操作,直至图中所有顶点皆被访问,即存储顶点的队列为空,表示已经没有未被访问的顶点加入队列。

    示例演示

    对于有向图 digraph,图的顶点集合和边集合如下:

    V = \{1,2,3,4,5\}
    E =\{<1,2>,<1,3>,<1,4>,<2,3>,<3,1>,<3,5>,<4,3>\}

    digraph

    step 1:

    选择 3 作为起始顶点,此时:
    队列元素:3
    已访问元素:3

    step 2:

    顶点 3 出队,将顶点 3 周围未被访问的顶点入队:
    队列元素:1,5
    已访问元素:3,1,5

    cycle 1:

    顶点 5 出队,将顶点 5 周围未被访问的顶点入队:
    队列元素:1
    已访问元素:3,1,5

    cycle 2:

    顶点 1 出队,将顶点 1 周围未被访问的顶点入队:
    队列元素:2,4
    已访问元素:3,1,5,2,4

    cycle 3:

    顶点 4 出队,将顶点 4 周围未被访问的顶点入队:
    队列元素:2
    已访问元素:3,1,5,2,4

    cycle 4:

    顶点 2 出队,将顶点 2 周围未被访问的顶点入队:
    队列元素:
    已访问元素:3,1,5,2,4

    参考代码
    def bfs(index, graph):
        queue, flag = Queue(), [False] * graph.number
        queue.put(index)  # save the node index
        flag[index - 1] = True  # indicates whether the node has been visited
        while not queue.empty():
            node = graph.list[queue.get() - 1]
            while node:
                if not flag[node.index - 1]:
                    queue.put(node.index)
                    flag[node.index - 1] = True
                node = node.next
    

    程序中存在两层循环,第一层循环为判断存储顶点的队列是否为空,因为要对队列中的每个顶点执行访问其相邻顶点操作,所以若队列不为空,则表示还有顶点的相邻顶点未进行访问。第二层循环为判断相邻顶点状态,并执行入队操作。

    性能分析

    根据参考代码和演示示例可知,对于图中每个顶点的操作类型有如下几种,入队、出队、设置已访问状态以及扫描顶点邻接表。因为对于每个顶点以上操作只发生一次,所以入队、出队和已访问状态设置,时间复杂度为 O(|V|),根据邻接表的介绍可知,|V| 个顶点的邻接表,存储的总顶点个数为 |E|2|E|,所以广度优先遍历的时间复杂度为 O(|V|+|E|)bfs 算法过程中,需要申请 O(|V|) 的数组记录顶点的访问状态,需要申请 O(|V|) 的队列空间存储顶点,且根据邻接表的内容可知,使用邻接表作为存储结构的空间复杂度为 O(|V|+|E|),所以广度优先遍历的空间复杂度为 O(|V|+|E|)

    深度优先方式

    深度优先遍历图的方式,同样会访问一个顶点的所有相邻顶点,不过深度优先的方式为,首先访问一个相邻顶点,并继续访问该相邻顶点的一个相邻顶点,重复执行直到当前正在被访问的顶点出度为零,或者不存在未访问状态的相邻顶点,则回退到上一个顶点继续按照该深度优先方式访问。因为存在回溯行为,所以需要借助栈结构保存顶点,或者直接利用递归调用产生的方法栈帧来完成回溯。

    相对于广度优先访问,深度优先的方式更像是一条路走到黑,走不下去了再回到上个路口选择另外一条路。

    实现方式
    1. 选择起始顶点入栈,并标记为已访问;
    2. 当栈不为空时,选择栈顶元素作为目标顶点,若目标顶点存在未访问状态的相邻顶点,则将该相邻顶点入栈,并标记为已访问;若不存在未访问状态的相邻顶点,则执行出栈操作;
    3. 重复执行步骤 2。
    示例演示

    对于有向图 digraph,图的顶点集合和边集合如下:

    V = \{1,2,3,4,5\}
    E =\{<1,2>,<1,3>,<1,4>,<2,3>,<3,1>,<3,5>,<4,3>\}

    digraph

    step 1:

    选择 3 作为起始顶点,此时:
    栈元素:3
    已访问元素:3

    step 2:

    顶点 3 作为目标顶点,将顶点 3 相邻未访问状态的顶点入栈:
    栈元素:3,5
    已访问元素:3,5

    cycle 1:

    顶点 5 作为目标顶点,因为不存在相邻未访问状态的顶点,所以执行出栈操作:
    栈元素:3
    已访问元素:3,5

    cycle 2:

    顶点 3 作为目标顶点,将顶点 3 相邻未访问状态的顶点入栈:
    栈元素:3,1
    已访问元素:3,5,1

    cycle 3:

    顶点 1 作为目标顶点,将顶点 1 相邻未访问状态的顶点入栈:
    栈元素:3,1,4
    已访问元素:3,5,1,4

    cycle 4:

    顶点 4 作为目标顶点,因为不存在相邻未访问状态的顶点,所以执行出栈操作:
    栈元素:3,1
    已访问元素:3,5,1,4

    cycle 5:

    顶点 1 作为目标顶点,将顶点 1 相邻未访问状态的顶点入栈:
    栈元素:3,1,2
    已访问元素:3,5,1,4,2

    cycle 6:

    顶点 2 作为目标顶点,因为不存在相邻未访问状态的顶点,所以执行出栈操作:
    栈元素:3,1
    已访问元素:3,5,1,4,2

    cycle 7:

    顶点 1 作为目标顶点,因为不存在相邻未访问状态的顶点,所以执行出栈操作:
    栈元素:3
    已访问元素:3,5,1,4,2

    cycle 8:

    顶点 3 作为目标顶点,因为不存在相邻未访问状态的顶点,所以执行出栈操作:
    栈元素:
    已访问元素:3,5,1,4,2

    参考代码
    def dfs(index, graph):
        stack, flag = [], [False] * graph.number
        stack.append(index)  # save the node index
        flag[index - 1] = True  # indicates whether the node has been visited
        while len(stack) > 0:
            node, size = graph.list[stack[-1] - 1], len(stack)
            while node:
                if not flag[node.index - 1]:
                    stack.append(node.index)
                    flag[node.index - 1] = True
                    break
                node = node.next
            if size == len(stack):  # means no node append
                stack.pop()
    

    程序中存在两层循环,第一层循环为判断栈是否为空,因为深度优先的遍历方式存在回溯的行为,所以借助栈结构来完成回溯操作。当栈为空时,表示已经回溯到起始顶点,且没有未访问状态的相邻顶点入栈,即图中所有顶点皆被访问过。第二层循环为对目标顶点的相邻顶点进行扫描,若存在未访问的相邻顶点,则将该相邻顶点入栈,并标记为已访问;若不存在,则执行出栈操作。

    这里提供另外一种实现方式,通过函数递归调用形成的方法栈帧完成回溯操作:

    def dfs(index, graph, flag):
        node, flag[index - 1] = graph.list[index - 1], True
        while node:
            if not flag[node.index - 1]:
                dfs(node.index, graph, flag)
            node = node.next
    
    性能分析

    根据参考代码和演示示例可知,对于图中每个顶点的操作类型有如下几种,入栈、出栈、设置已访问状态以及扫描顶点邻接表。对于入栈、出栈以及设置访问状态操作,每个顶点只会执行一次。根据程序中第二层循环的实现可知,对每个顶点的相邻顶点扫描只会全扫描一次,扫描结束即发生回溯。所以深度优先遍历的时间复杂度为 O(|V|+|E|)dfs 算法过程中,需要申请 O(|V|) 的数组记录顶点的访问状态,需要申请 O(|V|) 的栈空间存储顶点,且根据邻接表的内容可知,使用邻接表作为存储结构的空间复杂度为 O(|V|+|E|),所以深度优先遍历的空间复杂度为 O(|V|+|E|)

    github 链接:广度优先与深度优先

    相关文章

      网友评论

        本文标题:数据结构(九):广度优先与深度优先

        本文链接:https://www.haomeiwen.com/subject/ichzzftx.html