[数据结构与算法]使用python实现简单的深度优先搜索，通俗易懂

图的深度优先搜索

1.利用栈实现
2.从源节点开始把节点按照深度放入栈，然后弹出
3.每弹出一个点，把该节点下一个没有进过栈的邻接点放入栈
4.直到栈变空

代码

# 定义节点
class Node:
    
    def __init__(self,value=None,connect=[]):
        
        self.value=value
        self.connect=connect   # 节点连接的其他节点集合
        
    def setValue(self,value):
        self.value=value
        
    def getValue(self):
        return self.value
    
    def setConnect(self,connect):
        self.connect=connect
        
    def getConnect(self):
        return self.connect
    
    def addConnect(self,node):
        self.connect.append(node)

# 深度优先
def dfs(node=None):
    if node is None:
        return
    
    nodeSet=set()  # 定义登记节点集合
    stack=[]   # 用List来表示栈
    
    print(node.getValue())  # 打印节点的值
    nodeSet.add(node)  # 登记遍历过的节点
    stack.append(node) # 将节点压入栈
    
    while len(stack)>0:
        
        cur=stack.pop()  # 将list中最末尾的元素删除，并返回元素值
        
        for next in cur.getConnect():   # 遍历该节点的邻接节点
            
            if next not in nodeSet:     # 如果该节点还没登记
                print(next.getValue())  # 打印邻接节点的值
                
                nodeSet.add(next)       # 登记邻接节点
                stack.append(cur)      # 将节点再次压入
                stack.append(next)     # 将邻接节点压入  
                break  # 退出，保持深度优先