DFS算法（python）_python dfs

深度优先搜索算法 （英语： Depth-First-Search ， DFS ）是一种用于遍历或搜索 树 或 图 的 算法 。. 这个算法会尽可能深的搜索树的分支。. 当节点v的所在边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。

这个也是我们在数据结构中学过的，我在这也不赘述。不明白原理的可以查一下DFS算法。

我们俗称的不撞南墙不回头。

如上图，我们选择A做第一个，我们得到的是ACEDFB。其实这里的代码跟BFS用到的代码一样，只需要修改一下即可。接下来我们用代码实现。

grap = {
    "A":["B","C"],
    "B":["A","C","D"],
    "C":["A","B","D","E"],
    "D":["B","C","E","F"],
    "E":["C","D"],
    "F":["D"]
}
#存图
 
def DFS(grap,star):                #DFS算法
    stack = []                     #定义一个栈
    seen = set()                   #建立一个集合，集合就是用来判断该元素是不是已经出现过
    stack.append(star)             #将任一个节点放入
    seen.add(star)                 #同上
    while (len(stack)>0) :         #当队列里还有东西时
        ver =  stack.pop()         #取出栈顶元素       !!!!这里也就是与BFS的不同
        notes = grap[ver]          #查看grep里面的key,对应的邻接点
        for i in notes:            #遍历邻接点
            if i not in seen:      #如果该邻接点还没出现过
                stack.append(i)    #存入stack
                seen.add(i)        #存入集合
        print(ver)                 #打印栈顶元素
 
 
print(DFS(grap,"A"))