深度优先算法（DFS）

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

深度优先算法

1、算法概述

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

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

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

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

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

2、原理详解

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

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

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

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

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

先给出一个图：

假设选定节点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