03-搜索与图论python

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())