深度优先遍历(Depth First Search)的主要思想是：

思想：不撞南墙不回头

1、首先以一个未被访问过的顶点作为起始顶点，沿当前顶点的边走到未访问过的顶点；

2、当没有未访问过的顶点时，则回到上一个顶点，继续试探别的顶点，直至所有的顶点都被访问过。

邻接表表示：

在这里我们采用数组+链表（头插法）表示邻接表

# a和b存在一条边
def add(a,b):
    e[idx] = b # e数组存放值
    nxt[idx] = h[a] # nxt存放下一个节点位置
    h[a] = idx # h 表示节点数组
    idx += 1 # 每个节点对应的唯一索引

核心算法：

# u 表示 访问的节点
def dfs(u)
    st[u] = True # st 标记数组 标记节点是否访问
    i = h[u]
    while i != -1:
        j = e[i]
        if !st[j]:
            dfs(j)
        i = nxt[i]

完整算法：

import numpy as np

def main():
    global e,nxt,h,idx,st
    idx = 0
    n = int(input("请输入整数n:"))
    e = np.full((n,),-1,dtype=int)
    nxt = np.full((n,),-1,dtype=int)
    h = np.full((100,),-1,dtype=int)
    st = np.full((100,),False,dtype=bool) #标记数组
    m = n-1
    while m:
        a = int(input("请输入a:"))
        b = int(input("请输入b:"))
        add(a,b)
        m -= 1
    dfs(1)

# 头插法建立链表
def add(a,b):
    global idx
    e[idx] = b
    nxt[idx] = h[a]
    h[a] = idx
    idx += 1
# 深度优先
def dfs(u):
    st[u] = True
    i = h[u]
    while i!=-1:
        j = e[i]
        if st[j] == False:
            dfs(j)
        i = nxt[i]
        
if __name__ == '__main__':
    main()

数据结构——DFS深度优先遍历

深度优先遍历(Depth First Search)的主要思想是：