数据结构——DFS深度优先遍历
深度优先遍历(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() 
基恩士成长空间 450人发布
