深度优先算法（DFS） - wpsshop博客
devbox
神奇cpp
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

深度优先算法（DFS）

作者：神奇cpp | 2024-07-21 02:44:18

赞

踩

深度优先算法

根据访问节点的顺序与方式，可以分为广度优先算法（BFS）和深度优先算法（DFS），本文介绍深度优先算法：

深度优先算法

1、算法概述

深度优先搜索属于图算法的一种，英文缩写为DFS。其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次。

深度优先搜索是一种在开发爬虫早期使用较多的方法，它的目的是要达到被搜索结构的叶结点(即那些不包含任何超链的HTML文件) 。

它的思想：
a.访问顶点v；

b.依次从v的未被访问的邻接点出发，对图进行深度优先遍历；直至图中和v有路径相通的顶点都被访问；

c.若此时图中尚有顶点未被访问，则从一个未被访问的顶点出发，重新进行深度优先遍历，直到图中所有顶点均被访问过为止。

2、原理详解

（深度优先搜索用栈（stack）来实现，整个过程可以想象成一个倒立的树形）
1、把根节点压入栈中。

2、每次从栈中弹出一个元素，搜索所有在它下一级的元素，把这些元素压入栈中。并把这个元素记为它下一级元素的前驱。

3、找到所要找的元素时结束程序。

4、如果遍历整个树还没有找到，结束程序。

本文中，我们使用深度优先算法给图做一个遍历，从而介绍它的原理：

先给出一个图：
gei

假设选定节点A为根节点,将根节点A放入栈中。从栈中取出节点A，寻找到A的子节点B、C并放入栈中。（此时处于节点A）

从栈中取出节点B，寻找B的子节点D，放入栈中。（此时处于节点B）

取出节点D，寻找子节点F并放入栈中。

下一步取出节点F重复执行以上操作，直至遍历全图。

需要注意的是：

  • 当一个节点有多个子节点，子节点入栈的顺序是随机的，也就是说同样一个图，可以产生多种结果。
  • 走到节点F时，会发现F没有子节点，那么此时就会回跳到F的父节点，并寻找一个尚未走过的节点（若父节点没有尚未走过的子节点，则继续回跳），回跳的过程可以不用表述。

3、代码描述

# -*- coding: utf-8 -*-
"""
Created on Sun Mar 31 16:56:06 2019

@author: King
"""

graph = {
        'A':['B','C'],
        'B':['A','C','D'],
        'C':['A','B','D','E'],
        'D':['B','C','E','F'],
        'E':['C','D'],
        'F':['D']
        }

def DFS(graph,start):
    stack = list(start) #将起始节点放入栈
    closed = set() #创建一个集合，存放已经走过的节点
    closed.add(start)
    while(len(stack)>0):
        vertex = stack.pop() #从栈取出一个节点
        nodes = graph[vertex]
        #判断节点是否走过
        for node in nodes:  
            if node not in closed:
                #若节点没有走过，则放入栈与集合
                stack.append(node) 
                closed.add(node)
        print(vertex,end='\t')

DFS(graph,'A') 

'''
若以A为根节点，那么遍历的结果可以是：
A       C       E       D       F       B 
'''

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/神奇cpp/article/detail/859379
推荐阅读
相关标签