1-DFS
排列数字
N=10
path=[0]*N
state=[False]*N
def dfs(u):
if u==n:
for i in range(n):
print(path[i],end=' ')
print()
for i in range(n):
if state[i]==False:
path[u]=i+1
state[i]=True
dfs(u+1)
#恢复现场
path[u]=0
state[i]=False
n=int(input())
dfs(0)
采用位运算太优雅了，细细体会。
N=10
path=[0]*N #记录路径
def dfs(u,state): #state-状态
if u==n: #递归到最后一个数
for i in range(n):
print(path[i],end=' ')
print()
for i in range(n):
if not (state>>i&1):
path[u]=i+1
dfs(u+1,state+(1<<i))
n=int(input())
dfs(0,0)
n皇后问题
方式一全排列方式
对于之前的我来说这个完全是不懂啊。。现在好一些了&—&
def dfs(x):
#开始检索第x行该如何填皇后
if x==n:
for i in range(n):
for j in range(n):
print(chessboard[i][j],end='')
print()
print()
#开始寻找第x行中的那一列，能合法填皇后的位置
for y in range(n):
if not col[y] and not dg[y+x] and not udg[y-x+n]: #y=x+b=>b=y-x+n y=-x+b=>b=x+y
chessboard[x][y]='Q'
col[y]=1
dg[y+x]=1
udg[y-x+n]=1
dfs(x+1) #开始观察x+1行
#回溯
udg[y-x+n]=0
dg[y+x]=0
col[y]=0
chessboard[x][y]='.'
if __name__=="__main__":
N=10
n=int(input())
chessboard=[['.' for _ in range(N)] for _ in range(N)]
#哪些列，主/副对角线不符合条件
col=[0]*N
dg=[0]*(2*N)
udg=[0]*(2*N)
dfs(0)
方法2-暴力枚举
将不放皇后的分支放在前面会超时。必须要有return
def dfs(x,y,queen):
if y==n:
#如果越界，考虑下一行的第一列
y=0
x+=1
if x==n:
#填完了所有的皇后输出答案
if queen==n:
for i in range(n):
for j in range(n):
print(chessboard[i][j],end='')
print()
print()
return #没有填完所有的皇后，说明该不是所求解
#开始对每个格子的情况进行枚举
#分支：放皇后，开始在x,y位置填=皇后
if not row[x] and not col[y] and not dg[y-x+n] and not udg[y+x]:
chessboard[x][y]='Q'
row[x],col[y],dg[y-x+n],udg[y+x]=1,1,1,1
dfs(x,y+1,queen+1)
row[x],col[y],dg[y-x+n],udg[y+x]=0,0,0,0
chessboard[x][y]='.'
#分支：不放皇后
dfs(x,y+1,queen)
if __name__=='__main__':
N=10
n=int(input())
chessboard=[['.' for _ in range(N)] for _ in range(N)]
row=[0]*N
col=[0]*N
dg=[0]*2*N
udg=[0]*2*N
dfs(0,0,0)
BFS
走迷宫
def bfs():
dx=[-1,0,1,0] #控制走的方向
dy=[0,1,0,-1]
queue=[(0,0)]
trace[0][0]=0
while queue:
x,y=queue.pop(0)
if (x,y)==(n-1,m-1): #到达左下角
return trace[x][y]
for i in range(4): #枚举四个方向
a=x+dx[i]
b=y+dy[i] #得到向上下左右走一步之后的坐标。
if 0<=a<n and 0<=b<m and graph[a][b]!=1 and trace[a][b]==-1:
#如果这个点是合法路劲，且以前没有走过
queue.append((a,b)) #将可以走通的路径的下一个点加入队列
trace[a][b]=trace[x][y]+1 #在trace做一个标记。
n,m=map(int,input().split())
N=101
graph=[[0]*N for _ in range(N)] #地图
trace=[[-1]*N for _ in range(N)]
for i in range(n):
graph[i][0:m]=list(map(int,input().split()))
print(bfs())
八数码
from collections import deque
dx=[-1,0,1,0]
dy=[0,1,0,-1]
def bfs(start):
end='12345678x'
#记录每个状态的交换次数，初始状态为0
d={
start:0}
q=deque([start]) #记录队列头节点到了哪个状态
while len(q):
#头节点出队
t=q.popleft()
#保存当前头节点距离初始状态的交换次数
distance=d[t]
if t==end:
return distance
#找下表，交换顺序
idx=t.find('x')
x=idx//3 #将一维坐标转换为二维坐标
y=idx%3
for i in range(4):
a=x+dx[i]
b=y+dy[i]
if 0<=a<3 and 0<=b<3:
t=list(t) #字符串不能交换，转换为列表交换
t[idx],t[a*3+b]=t[a*3+b],t[idx]
t=''.join(t)
if t not in d: #如果心得状态不在字典里
d[t]=distance+1 #添加新状态进入字典并赋值为上一个状态的交换次数+1
q.append(t) #将新的状态入队
#回退状态
t=list(t)
t[idx],t[a*3+b]=t[a*3+b],t[idx]
t=''.join(t)
return -1
n=input().split()
start=''
for c in n:
start+=c
print(bfs(start))
树与图的深度优先遍历
树的重心
N=100010
M=2*N #以有向图的格式存储无向图，所以每个节点至多对应2n-2条边
e=[0]*M
ne=[0]*M
h=[-1]*N #邻接表存储树，有n个节点，所以需要n个队列头节点
idx=0
st=[False]*N #记录节点是否被访问过，访问过则标记为true
ans=N #表示重心的所有的子树中，最大的子树的结点数目
def add(a,b): #a所对应的单链表中插入b a作为根
global idx
e[idx]=b
ne[idx]=h[a]
h[a]=idx
idx+=1
#表示u节点包含的最大连通块的点的个数
def dfs(u):
global ans
st[u]=True
sum=1 #节点的个数，起始值为自身节点的一个
res=0 #用来比较最大连通块的点的个数
i=h[u]
while i!=-1:
j=e[i]
if not st[j]:
s=dfs(j)
res=max(res,s)
sum+=s
i=ne[i]
#即最大的连通块点的个数
res=max(res,n-sum)
#结果取最小的连通块的个数
ans=min(ans,res)
return sum
n=int(input())
for i in range(n-1): #树中是不存在环的，对于有n个节点的树，必定是n-1条边
a,b=map(int,input().split())
add(a,b)
add(b,a)
dfs(1)
print(ans)
图中点的层数
N=100010
e=[0]*N #存储元素
ne=[0]*N #存下一个节点的位置
h=[-1]*N #存储树
idx=0 #每个节点的独特身份证
q=[0]*N #队列
d=[-1]*N #该节点到1号点的距离
def add(a,b): #构建树
global idx
e[idx]=b
ne[idx]=h[a]
h[a]=idx
idx+=1
def bfs():
hh,tt=0,0 #队头，队尾
q[0]=1 #入队1号结点
d[1]=0 #1号节点到本身的距离为0
while hh<=tt:
x=q[hh]
hh+=1 #出队列
i=h[x] #i指向头节点
while i!=-1: #遍历该结点的孩子结点
j=e[i] #取出该节点元素
if d[j]==-1: #该结点没有被遍历过
d[j]=d[x]+1 #更新该结点距离1号点的距离
tt+=1 #处理完该结点，入队列，以便后续来处理该结点的孩子结点
q[tt]=j
i=ne[i] #指向下一个节点，也就是该结点的孩子结点。
return d[n]
n,m=map(int,input().split())
for i in range(m):
a,b=map(int,input().split())
add(a,b)
print(bfs())
拓补排序
N = 100010
e = [0]*N
ne = [0]*N
h = [-1]*N
idx = 0
# 入队
q = [0]*N
# 入度
d = [0]*N
def add(a,b):
global idx
e[idx] = b
ne[idx] = h[a]
h[a] = idx
idx += 1
def topsort():
hh,tt = 0, -1
# 点的编号是 1到 n，如果有入度为0的点，则把它入队
for i in range(1,n+1):
if not d[i]:
tt += 1
q[tt] = i
while hh <= tt:
t = q[hh]
hh += 1
i = h[t]
while i != -1:
j = e[i]
# 入度减一
d[j] -= 1
if d[j] == 0:
tt += 1
q[tt] = j
i = ne[i]
return tt == n - 1
n,m = map(int,input().split())
while m:
m -= 1
a,b = map(int,input().split())
# 添加从a -> b 的一条边，b的入度 + 1
add(a,b)
d[b] += 1
if topsort(): #如果是拓补序列。
for i in range(n):
print(q[i],end=" ")
else:
print(-1)
朴素Dijkstra算法
N = 510
# 因为题目的边远大于点，因此是稠密图，稠密图用邻接矩阵去存。
d = [[0x3f3f3f3f]*N for _ in range(N)]
# dist为每个点到起点的距离
dist = [0x3f3f3f3f]*N
# st表示每个点的最短距离已经确定了
st = [False]*N
def dijkstra():
dist[1] = 0
# 迭代 n - 1 次，因为每迭代一次，一个点的最短距离就确定了，并把它加入到确定的集合当中。
# 前 n - 1 个点已经确定，那么最后一个点自然也就是最短距离了，所以可以把 n 改成 n - 1
for i in range(n-1):
# 随便定义一个点，主要是为了后面比较，然后找到最小距离的点
t = -1
# 循环每个点，找到最短距离的点，并把它赋值给 t
for j in range(1,n+1):
if not st[j] and dist[j] < dist[t]:
t = j
# 标记该点距离确定
st[t] = True
# 根据该点更新其他所有点的距离
for j in range(1,n+1):
dist[j] = min(dist[j], dist[t] + d[t][j])
# 如果取到了最后一个点，则最后一个点的最短距离被找到，结束循环。
if t == n:
break
if dist[n] == 0x3f3f3f3f:
return -1
return dist[n]
n,m = map(int,input().split())
while m:
a,b,c = map(int,input().split())
d[a][b] = min(d[a][b], c)
m -= 1
print(dijkstra())
