深度优先搜索
1. 搜索过程
一个方向搜,不到黄河不回头,直到遇到绝境了,搜不下去了,再换方向(换方向的过程就涉及到了回溯)
2. 代码框架
回溯法的代码框架:
def backtracking(参数):
if 终止条件:
存放结果
return
for 选择本层集合中的元素(树中节点孩子的数量就是集合大小):
处理节点
backtracking(路径,选择列表) #递归
回溯,撤销处理结果
dfs的代码框架:
def dfs(参数):
if 终止条件:
存放结果
return
for 选择本节点连接的其他节点:
处理节点
dfs(图,选择的节点) #递归
回溯,撤销处理结果
3. dfs三部曲
(1)确定递归函数的参数,写递归函数时,需要什么参数,再补充
(2)终止条件,很多dfs写法,没有写终止条件,写在了dfs递归的逻辑
(3)处理目前搜索节点出发的路径,for循环遍历目前搜索节点所能到的所有节点
4. 题目
(1)所有可达路径
思路:首先需要用邻接表或邻接矩阵存储边,然后才能开始三部曲
dfs三部曲:
a. 递归的参数和返回值:图的数据结构,当前节点,终止节点;一般返回空
b. 终止条件:当当前节点到达终止节点时,存储路径
c. 递归逻辑:目前搜索节点所能到的所有节点
“所能到达”的含义,图的数据结构中节点路径存在
处理节点-递归-回溯
def dfs(graph,x,n):#参数:图,当前节点,终止节点
#终止条件:当前节点到达终止节点时,一般返回空
if x==n:
#存储路径
result.append(path[:])
return
for i in range(1,n+1):#遍历目前搜索节点所能到的所有节点
if graph[x][i]==1: #如果节点路径存在
path.append(i) #处理节点
dfs(graph,i,n)#递归
path.pop() #回溯,撤销结果
(2)岛屿数量
思路:先定义二维矩阵存储岛屿的数量graph,还需要一个矩阵记录岛屿的访问情况visited,初始化为False,然后进行dfs三部曲,最后求路径长度就是岛屿数量
dfs三部曲:
a. 递归函数的参数和返回值:参数有grapg, visited, 访问的坐标x和y,路径,返回值为空
b. 终止条件:遇到0或已经访问过的(visited[x][y]==True)
c. 递归:由于岛屿的遍历可以四个方向任意进行,因此依次遍历四个方向可搜索的节点(x-1,x+1,y-1,y+1),将当前节点设置为已访问过
“可搜索”的含义:下一个节点不越界
#深度优先搜索
def dfs(graph,visited,x,y,path): #参数:图数据结构、访问情况、当前节点的x和y坐标,路径
#终止条件:访问过或岛屿不存在,则path不改变
if visited[x][y] or graph[x][y]==0:
return path
#标记当前节点已访问,把当前节点加入到路径中
visited[x][y]=True
path.append((x,y))
for dir in dirs: #遍历四个方向上可到达的节点
nextnode=dir(x,y)
#可到达:判断下一个节点是否越界
if nextnode[0]<0 or nextnode[0]>=n or nextnode[1]<0 or nextnode[1]>=m:
continue
path=dfs(graph,visited,nextnode[0],nextnode[1],path)#递归
return path
(3)岛屿的最大面积
题目同上,输出描述:输出一个整数,表示岛屿的最大面积。如果不存在岛屿,则输出 0
思路:搜索每个岛屿上“1”的数量,然后取一个最大的
dfs三部曲:
a. 递归函数的参数和返回值:图的数据结构、访问情况、当前节点的横纵坐标,计数值,返回值为计数值
b. 终止条件:当前节点已访问过或节点不可到达,返回计数值0
c. 递归:由于岛屿的遍历可以四个方向任意进行,因此依次遍历四个方向可搜索的节点(x-1,x+1,y-1,y+1),并将当前节点设置为已访问过
“可搜索”的含义:下一个节点不越界
input1=list(map(int,input().split()))
n,m=input1[0],input1[1]#n表示行数,m表示每行数字个数
#存储岛屿信息
graph=[[0]*m for _ in range(n)]
for i in range(n):
input2=list(map(int,input().split()))
for j in range(m):
graph[i][j]=input2[j]
#四个方向
dirs=[
lambda x,y: (x+1,y),
lambda x,y: (x-1,y),
lambda x,y: (x,y+1),
lambda x,y: (x,y-1)
]
class IslandArea:
def countArea(self,graph):
res=0
visited=[[False]*m for _ in range(n)]
for i in range(n):
for j in range(m):
if graph[i][j]==1 and not visited[i][j]:#未访问过
count=0
c=self.dfs(graph,visited,i,j,count)
res=max(res,c)
return res
#深度优先遍历
def dfs(self,graph,visited,x,y,count): #参数:图的数据结构、访问信息,坐标x和y
#终止条件:访问过或岛屿不存在,返回0
if visited[x][y] or graph[x][y]==0:
return 0
visited[x][y]=True
count=1 #当前节点计数为1
for dir in dirs: #遍历四个方向上所能到达的节点
nextnode=dir(x,y)
#判断下一个节点是否越界
if nextnode[0]<0 or nextnode[0]>=n or nextnode[1]<0 or nextnode[1]>=m: continue
count+=self.dfs(graph,visited,nextnode[0],nextnode[1],count)#递归
return count
IslandArea1 = IslandArea()
print(IslandArea1.countArea(graph))
(4)孤岛的总面积
孤岛是那些位于矩阵内部、所有单元格都不接触边缘的岛屿。现在你需要计算所有孤岛的总面积,岛屿面积的计算方式为组成岛屿的陆地的总数。
思路:接触边缘:即判断节点是否越界,如果越界,则标记一整块岛屿(使用flag);计算孤岛面积:对非孤岛的“1”进行计数(使用count),因此本题需要增加两个参数
dfs三部曲:
a. 递归函数的参数和返回值:参数有:岛屿数据、访问情况,当前节点的横纵坐标,flag,count;需要返回flag,判断是否接触边缘,如果没有接触边缘,则对count进行累加
b. 终止条件:如果访问过或者岛屿不存在,则返回0和flag(不改变flag值)
c. 递归:按四个方向依次遍历,判断节点是否越界,如果越界,则标记flag=True,遍历下一个方向的节点;否则,递归,对计数值进行累加
#输入输出、方向、图数据和之前代码相同
#深度优先搜索
def dfs(graph,visited,x,y,count,flag): #参数:图数据结构、访问情况、当前节点的x和y坐标,计数,标记
#终止条件:访问过或岛屿不存在,则岛屿计数值为0,flag不改变
if visited[x][y] or graph[x][y]==0:
return 0,flag
#标记当前节点已访问,当前节点计数为1
visited[x][y]=True
count=1
for dir in dirs: #遍历四个方向上可到达的节点
nextnode=dir(x,y)
#可到达:判断下一个节点是否越界,如果越界,一整块标记为边缘
if nextnode[0]<0 or nextnode[0]>=n or nextnode[1]<0 or nextnode[1]>=m:
flag=True
continue
c,flag=dfs(graph,visited,nextnode[0],nextnode[1],count,flag)#递归
count+=c
return count,flag
visited=[[False]*m for _ in range(n)] #记录访问情况
res=0
for i in range(n):
for j in range(m):
if graph[i][j]==1 and not visited[i][j]: #未访问
count=1
flag=False
count,flag=dfs(graph,visited,i,j,count,flag)
if not flag: res+=count
print(res)
(5)沉没孤岛
孤岛是那些位于矩阵内部、所有单元格都不接触边缘的岛屿。现在你需要将所有孤岛“沉没”,即将孤岛中的所有陆地单元格(1)转变为水域单元格(0);输出将孤岛“沉没”之后的岛屿矩阵。 注意:每个元素后面都有一个空格
思路:接触边缘,即节点越界,则标记一整块岛屿(使用flag);需要修改孤岛的单元数值,则记录不接触边缘的岛屿路径,然后将路径上的点设置为0(使用path),因此本题需要增加两个参数
dfs三部曲:
a. 递归函数的参数和返回值:参数有岛屿数据graph、访问情况visited、当前节点坐标x和y、接触边缘的标记flag、岛屿路径path;需要返回flag,如果没有接触边缘,则将path上的节点修改为0
b. 终止条件:访问过或者岛屿不存在,不改变flag和path
c. 递归:依次遍历四个方向,判断每个方向上的下一个节点是否越界,如果越界,则令flag=True,即标记整块岛屿接触边缘;否则,进行递归,收集节点路径。
最后对flag=False的路径上的节点数值进行修改
#其他部分的定义和之前代码相同
#深度优先搜索
def dfs(graph,visited,x,y,flag,path): #参数:图数据结构、访问情况、当前节点的x和y坐标,标记,路径
#终止条件:访问过或岛屿不存在,则path和flag不改变
if visited[x][y] or graph[x][y]==0:
return flag,path
#标记当前节点已访问,把当前节点加入到路径中
visited[x][y]=True
path.append((x,y))
for dir in dirs: #遍历四个方向上可到达的节点
nextnode=dir(x,y)
#可到达:判断下一个节点是否越界,如果越界,一整块标记为边缘
if nextnode[0]<0 or nextnode[0]>=n or nextnode[1]<0 or nextnode[1]>=m:
flag=True
continue
flag,path=dfs(graph,visited,nextnode[0],nextnode[1],flag,path)#递归
return flag,path
visited=[[False]*m for _ in range(n)] #记录访问情况
for i in range(n):
for j in range(m):
if graph[i][j]==1 and not visited[i][j]: #未访问
flag=False
path=[] #记录路径
#flag,path=dfs(graph,visited,i,j,flag,path)
flag,path=bfs(graph,visited,i,j,flag,path)
if not flag: #如果不是边缘,则将路径中的点置为0
for tup in path:
graph[tup[0]][tup[1]]=0
#输出
for i in range(n):
lst=list(map(str,graph[i]))
s=' '.join(lst)
print(s)
(6)水流问题
思路:
方法一:遍历每个点,看看该点能否同时到达第一组边界和第二组边界
方法二:从第一组边界和第二组边界出发,记录访问情况,对于两组边界都能访问的点则为结果
dfs三部曲:
a. 递归函数的参数和返回值:地形数据、访问情况、当前节点的横纵坐标,返回值为空
b. 终止条件:当已访问过时,返回
c. 递归:对于当前节点记为已访问,遍历四个方向上的下一个节点,判断下一个节点是否越界,如果越界则跳过该点;否则,进一步判断下一个节点是否为低处,如果为低处则跳过该点(目标是到达对边),否则,递归
#其他代码和之前相似
def dfs(grid, visited, x, y):
direct = [[1,0], [0,1],[-1,0],[0,-1]]
if visited[x][y]:
return
visited[x][y] = True
for i in range(4):
next_x = x + direct[i][0]
next_y = y + direct[i][1]
if next_x < 0 or next_x >= len(grid) or next_y < 0 or next_y >= len(grid[0]):
continue
if grid[x][y] > grid[next_x][next_y]:
continue
dfs(grid, visited, next_x, next_y)
return
# 深度遍历搜索主函数
fitst_border = [[False for _ in range(m)] for _ in range(n)]
second_border = [[False for _ in range(m)] for _ in range(n)]
for i in range(n):
dfs(grid, fitst_border, i, 0)
dfs(grid, second_border, i, m-1)
for i in range(m):
dfs(grid, fitst_border, 0, i)
dfs(grid, second_border, n-1, i)
for i in range(n):
for j in range(m):
if fitst_border[i][j] and second_border[i][j]:
print(f"{i} {j}")
(7)有向图的完全可达性
dfs三部曲:
a. 递归函数的参数和返回值:参数有地图(访问当前节点下一个连接的节点)、访问情况(是否遍历完毕),当前节点
b. 终止条件:存在两个选择:出来当前访问节点还是出来下一个要访问的节点
对于当前访问节点,终止条件是判断当前节点是否访问过,如果是,则终止本层递归,否则,赋值为True;对于下一个要访问的节点,则不需要终止条件,而在第三步处理
c. 处理目前搜索节点出发的路径:本题不需要回溯,题目要求判断节点是否能到达所有节点,则将遍历过的节点标记即可(当需要搜索可行路径是才要回溯)
def dfs(graph, visited, key):
if visited[key]:
return
visited[key] = True
keys = graph[key]
for k in keys:
dfs(graph, visited, k)
广度优先搜索
1. 搜索过程
先把本节点所连接的所有节点遍历一遍,走到下一个节点的时候,再把连接节点的所有节点遍历一遍,搜索方向更像是广度,四面八方的搜索过程。
2. 使用场景
解决两个点之间的最短路径问题
3. 代码框架
dirs = [
lambda x, y: (x + 1, y), #lambda函数对x或y进行加减
lambda x, y: (x, y + 1),
lambda x, y: (x - 1, y),
lambda x, y: (x, y - 1)
]
def bfs(graph,visited,x,y):
#定义一个队列,存储遍历过的节点
queue=deque()
#当前节点加入队列并标记走过
queue.append((x,y))
visited[x][y]=True
while queue:
curNode=queue.pop() #当前节点
for dir in dirs: #遍历四个方向上能到达的节点
nextNode=dir(curNode[0],curNode[1])
#判断下一个节点是否越界
if nextNode[0] <0 or nextNode[0]>=n or nextNode[1] <0 or nextNode[1]>=m: continue
#如果能到达,判断下一个节点能否访问
if not visited[nextNode[0]][nextNode[1]] and graph[nextNode[0]][nextNode[1]]==1:
queue.append((nextNode[0],nextNode[1]))
visited[nextNode[0]][nextNode[1]]=True #只要队列加入节点,立即标记访问过
4. 题目
(1)岛屿数量
思路:广搜的模板题,遇到一个没有遍历过的节点陆地,计数器就加一,然后把该节点陆地所能遍历到的陆地都标记上。再遇到标记过的陆地节点和海洋节点的时候直接跳过。 这样计数器就是最终岛屿的数量
(2)岛屿的最大面积
思路:广搜的模板题,返回参数为count。遇到一个没有遍历过的节点陆地,计数器就加一,同时标记为访问过,每次保存最大的计数值,得到最大的岛屿面积
#其他部分代码和之前相同
#广度优先搜索
def bfs(graph,visited,x,y):
#定义一个队列存储遍历过的节点
queue=deque()
count=1
queue.append((x,y))
visited[x][y]=True
while queue:
curnode=queue.pop()
for dir in dirs: #遍历四个方向
nextnode=dir(curnode[0],curnode[1]) #下一个节点
#判断下一个节点能否到达,即是否越界
if nextnode[0]<0 or nextnode[0]>=n or nextnode[1]<0 or nextnode[1]>=m: continue
#判断下一个节点是否遍历过
if not visited[nextnode[0]][nextnode[1]] and graph[nextnode[0]][nextnode[1]]==1:
queue.append(nextnode)
visited[nextnode[0]][nextnode[1]]=True
count+=1
return count
visited=[[False]*m for _ in range(n)]
res=0
for i in range(n):
for j in range(m):
if not visited[i][j] and graph[i][j]==1:
count=bfs(graph,visited,i,j)
res=max(res,count)
print(res)
(3)孤岛的总面积
思路:广搜的模板题,与上一题的不同之处在于在越界的判断中添加flag=True,最后返回count和flag
#其他部分的代码同之前的和dfs对应题目相同
#广度优先搜索
def bfs(graph,visited,x,y,count,flag):
#定义一个队列用于存储遍历过的节点
queue=deque()
queue.append((x,y))
#一旦加入队列立即标记
visited[x][y]=True
while queue:
curnode=queue.pop() #当前节点
#依次遍历四个方向上的节点
for dir in dirs:
nextnode=dir(curnode[0],curnode[1])#下一个节点
#判断下一个节点是否越界
if nextnode[0]<0 or nextnode[0]>=n or nextnode[1]<0 or nextnode[1]>=m:
flag=True #标记为一整块都在边缘
continue
#判断下一个节点是否访问过或者是否为水地
if not visited[nextnode[0]][nextnode[1]] and graph[nextnode[0]][nextnode[1]]==1:
visited[nextnode[0]][nextnode[1]]=True #立即标记
queue.append(nextnode) #加入队列
count+=1
return count,flag
(4)沉没孤岛
思路:广搜的模板题,与上一题的不同之处在于,没有count,而是增加了path,用于收集节点
#其他部分的定义同dfs对应题目相同
#广度优先搜索
def bfs(graph,visited,x,y,flag,path):
#定义一个队列用于存储遍历过的节点
queue=deque()
queue.append((x,y))
#一旦加入队列立即标记,加入路径
visited[x][y]=True
path.append((x,y))
while queue:
curnode=queue.pop() #当前节点
#依次遍历四个方向上的节点
for dir in dirs:
nextnode=dir(curnode[0],curnode[1])#下一个节点
#判断下一个节点是否越界
if nextnode[0]<0 or nextnode[0]>=n or nextnode[1]<0 or nextnode[1]>=m:
flag=True #标记为一整块都在边缘
continue
#判断下一个节点是否访问过或者是否为水地
if not visited[nextnode[0]][nextnode[1]] and graph[nextnode[0]][nextnode[1]]==1:
visited[nextnode[0]][nextnode[1]]=True #立即标记
queue.append(nextnode) #加入队列
path.append(nextnode) #加入路径
return flag,path
(4)字符串接龙
思路:题目要求最短路径,因此使用广度优先搜索。创建一个字典visited记录当前字符串的所在路径的长度,比如从beginstr出发,路径path记为1;遍历当前单词的每个字符,用26个字母逐个替换,如果替换后的字符串等于endstr,则返回path+1;否则,如果出现在strlist,但未出现在visited中,则令visited[new_word]=path+1;遍历完队列没找到,返回0
#广度优先搜索
def bfs(strlist,beginstr,endstr):
visited={beginstr:1}
queue=deque([beginstr]) #初始化队列
while queue:
word=queue.popleft()
path=visited[word]
#遍历这个字符串的每个字符
for i in range(len(word)):
#逐个替换
for j in range(26):
newword=word[:i]+chr(ord('a')+j)+word[i+1:]
if newword==endstr: #若替换字母后的单词等于终点字符串
return path+1
#若替换字母后的单词在字典中但不在访问情况中
if newword in strlist and newword not in visited:
visited[newword]=path+1
queue.append(newword)
#没找到则输出0
return 0
其他题目
(1)岛屿的周长
思路:计数总的岛屿数量,由于每个岛屿四条边,总变数为 岛屿数量*4,如果存在一对相邻岛屿,那么边数就要减2,因此需要计数相邻岛屿对数。岛屿周长=岛屿数量*4-相邻岛屿对数*2
如何不重复地统计相邻岛屿对数呢?只统计上边和左边也为岛屿的数量
count=0 #记录岛屿数量
neib=0 #记录相邻岛屿数量
#周长=岛屿数量*4-相邻岛屿数量*2 (有一对相邻两个陆地,边的总数就要减2)
for i in range(n):
for j in range(m):
#判断是否为陆地
if graph[i][j]==1:
count+=1
#统计上边和左边相邻岛屿数量,不统计下边和右边,避免重复
if i>0 and graph[i-1][j]==1:
neib+=1
if j>0 and graph[i][j-1]==1:
neib+=1
print(count*4-neib*2)
并查集理论基础
1. 解决问题
判断两个元素是否在同一个集合
并查集有两个功能:①将两个元素添加到一个集合;②判断两个元素在不在同一个集合
2. 原理讲解
(1)如何将2个元素添加到同一个集合?
例如:将A, B, C放在同一个集合,即将三个元素联通一起,使用一个一维数组,father[A]=B, father[B]=C. 寻根思路,只要A, B, C在同一个根下就是同一个集合
A是下标,father[A]=B, 因此A的根是B,而father[B]=C,B的根是C,则A,B的根都是C,令father[C]=C,C的根也为C,因此就表示出A,B,C都在同一个集合里
father数组初始化时要father[i]=i,自己指向自己
(2)如何判断两个元素是否在同一个集合?
通过find函数找到两个元素属于同一个根,则说明两个元素就是同一个集合
3. 路径压缩
构造多叉树,使非根节点的所有节点直接指向根节点
实现:令father[u]接住递归函数find(father[u])的返回结果,让节点u的父节点变成根节点
4. 代码模板
class joinSet:
#并查集的初始化 father[i]=i
def init(self,father,nodes):
for i in range(1,nodes):
father[i]=i
#并查集里寻根的过程
def find(self,node,father):
if node==father[node]:
return node
else:
node=self.find(father[node],father)
return node
#判断node1和node2是否找到同一个根
def isSame(self,node1,node2,father):
node1=self.find(node1,father)
node2=self.find(node2,father)
return node1==node2
#将node1->node2 这条边加入并查集
def join(self,node1,node2,father):
node1=self.find(node1,father)
node2=self.find(node2,father)
if node1==node2:
return
father[node1]=node2
5. 题目
(1)寻找存在的路径
思路:并查集的模板题,首先初始化一个一维数组,然后遍历每条边,通过使用join函数将每条边加入到并查集,最后isSame函数判断是否是同一个根。在模板中,只需要修改n的大小即可
#实例化对象
joinSet_instance=joinSet()
nodes,edges=map(int,input().split()) #节点个数、边数
father=[0]*(nodes+1)
#初始化father
joinSet_instance.init(father,nodes+1)
#连接节点
for i in range(edges):
node1,node2=map(int,input().split())
joinSet_instance.join(node1,node2,father)
#最后一行包含两个正整数
start,end=map(int,input().split())
if joinSet_instance.isSame(start,end,father): #如果两个节点的根相同,表示能到达
print(1)
else:
print(0)
(2)冗余连接
思路:并查集的模板题,并查集解决判断两个节点是否在同一个集合内,或者将两个节点添加到一个集合中。从前向后遍历每一条边,边的两个节点如果不在同一个集合,就加入集合;如果边的两个节点已经出现在同一个集合里(同一个根),说明着边的两个节点已经连在一起了,再加入这条边一定就出现环了。
(3)冗余连接Ⅱ
思路:与题(2)的区别在于本题是有向图,本题的本质是:有一个有向图,是由一颗有向树 + 一条有向边组成的 (所以此时这个图就不能称之为有向树),现在让我们找到那条边 把这条边删了,让这个图恢复为有向树。存在两种情况:
情况一:入度为2的点,需先判断删除哪一条边,删除后本图能成为有向树,优先删除靠后的边
情况二:没有入度为2的点,说明图中有环,此时删除构成环的点即可
因此首先需要统计节点入度,首先如果没有入度为2的点,退化成为题(2)使用isSame判断是否成环;如果存在入度为2的点,先删除两条边,对一条边判断,若在join()前就已经连通了,就说明这条边是答案,否则,另一条边就是答案
edges=defaultdict(list)
flag=False
for i in range(n):
node1,node2=map(int,input().split())
if flag:
continue
edges[node2].append(node1)
#判断入度是否为2
if len(edges[node2])==2:
#判断在连接前是否连通
if joinSet_instance.find(node1,father)==joinSet_instance.find(node2,father):
print(node1,node2)
else:
print(edges[node2][0],node2)
flag=True
continue
#判断是否成环
if joinSet_instance.isSame(node1,node2,father):
flag=True
print(node1,node2)
joinSet_instance.join(node1,node2,father)
最小生成树
1. 最小生成树的定义
所有节点的最小连通子图,即以最小的成本(边的权值)将图中所有节点连接在一起,若图中有n个节点,一定可以用n-1条边将所有节点连接在一起。因此最小生成树算法就是如何选择这n-1条边
2. Prim算法(维护节点的集合)
采用贪心策略,每次寻找距离最小生成树最近的节点并加入到最小生成树中
prim三部曲
(1)选距离生成树最近节点
(2)最近节点加入生成树
(3)更新非生成树节点到生成树的距离(即更新minDist数组,minDist数组用来记录每一个节点距离最小生成树的最近距离)
代码模板
def prim_mst(v, edges):
# 初始化网格,使用最大浮点数作为默认的最大值
grid = [[float('inf') for _ in range(v + 1)] for _ in range(v + 1)]
# 添加边的权重到网格中
for edge in edges:
x, y, k = edge
grid[x][y] = k
grid[y][x] = k
# 初始化最小距离和是否在树中的列表
min_dist = [float('inf')] * (v + 1)
is_in_tree = [False] * (v + 1)
# 将第一个节点加入树中,初始化它的距离为0
min_dist[1] = 0
# 迭代v-1次,建立v-1条边
#(n个节点,一定可以用n-1条边将所有节点连接在一起)
for _ in range(v - 1):
# 第一步:选择距离生成树最近的节点
cur, min_val = -1, float('inf')
for j in range(1, v + 1):
if not is_in_tree[j] and min_dist[j] < min_val:
min_val = min_dist[j]
cur = j
# 第二步:将最近节点加入生成树
is_in_tree[cur] = True
# 第三步:更新非生成树节点到生成树的距离
for j in range(1, v + 1):
if not is_in_tree[j] and grid[cur][j] < min_dist[j]:
min_dist[j] = grid[cur][j]
# 计算MST的总权重
result = sum(min_dist[2:])
return result
3. Kruskal算法(维护边的集合)
kruscal的思路
(1)边的权值排序,优先选最小的边加入到生成树
(2)遍历排序后的边
- 如果边首尾的两个节点在同一个集合,说明如果连上这条边图中会出现环
- 如果边首尾的两个节点不在同一个集合,加入到最小生成树,并把两个节点加入同一个集合
在代码中如何判断两个节点是否在同一个集合?——并查集
代码
#使用krucial方法
class joinSet:
def init(self,nodes,father):
for i in range(1,nodes+1):
father[i]=i
def find(self,node,father):
if node==father[node]:
return node
else:
node=self.find(father[node],father)
return node
def isSame(self,node1,node2,father):
node1=self.find(node1,father)
node2=self.find(node2,father)
return node1==node2
def join(self,node1,node2,father):
node1=self.find(node1,father)
node2=self.find(node2,father)
if node1==node2:
return
father[node1]=node2
class Edges:
def __init__(self,left,right,value):
self.left=left
self.right=right
self.value=value
v,e=map(int,input().split())
#将每条边的信息存储起来
edges=[]
for i in range(e):
l,r,val=map(int,input().split())
edges.append(Edges(l,r,val))
# 按边的权值对边进行从小到大排序
edges.sort(key=lambda edge: edge.value)
#初始化并查集
father=[0]*(v+1)
js=joinSet()
js.init(v,father)
res=0
#遍历每条边,如果节点的祖先不同,则表示不在同一个集合
for edge in edges:
if not js.isSame(edge.left,edge.right,father):
js.join(edge.left,edge.right,father)
res+=edge.value
print(res)
Kruskal和prim的区别
prim维护的是节点的集合,而 Kruskal 维护的是边的集合。 如果 一个图中,节点多,但边相对较少,那么使用Kruskal 更优;因此在稀疏图中,用Kruskal更优,在稠密图中,用prim更优。
拓扑排序
1. 定义
给出一个有向无环图,把有向无环图转成线性的排序(依赖关系)
拓扑排序是图论中判断有向无环图的常用方法
2. 实现算法
BFS和DFS
3. 拓扑排序的过程
(1)找到入度为0的节点,加入结果集
(2)将该点从图中移除
循环上述两步,指导所有节点都在图中被移除,结果集的顺序就是拓扑排序顺序(不唯一)
4. 题目及代码
软件构建
from collections import deque,defaultdict
n,m=map(int,input().split()) #n个文件m条依赖关系
#入度表
indegree=[0]*n
#邻接表,记录边的依赖关系
graph=defaultdict(list)
for i in range(m):
v1,v2=map(int,input().split())
indegree[v2]+=1
graph[v1].append(v2)
#将入度为0的节点放入队列中
queue=deque([node for node in range(n) if indegree[node]==0])
#结果集
res=[]
while queue:
curnode=queue.popleft()
res.append(curnode)
for neighbour in graph[curnode]:
indegree[neighbour]-=1
if indegree[neighbour]==0:
queue.append(neighbour)
if len(res)==n:
print(' '.join(map(str,res)))
else:
print(-1)
最短路算法
1. dijkstra算法
不断寻找距离 源点 最近的没有访问过的节点(类似于Prim)
dijkstra三部曲
(1)选源点到哪个节点近且该节点未被访问过
(2)该最近节点被标记访问过
(3)更新非访问节点到源点的距离(即更新minDist数组,minDist用于记录每一个节点距离源点的最小距离)
题目与代码
参加科学大会
n,m=map(int,input().split())
graph=[[float('inf')]*(n+1) for _ in range(n+1)]
visited=[False]*(n+1)
minDist=[float('inf')]*(n+1)
minDist[1]=0
for _ in range(m):
v1,v2,val=map(int,input().split())
graph[v1][v2]=val
for _ in range(n):
#第一步:选择距离源点最近且未被访问过的节点
cur,min_val=1,float('inf')
for i in range(1,n+1):
if not visited[i] and minDist[i]<min_val:
min_val=minDist[i]
cur=i
#第二步:标记该节点为已访问过
visited[cur]=True
#第三步:更新非访问节点到源点的距离
for v in range(1,n+1):
if not visited[v] and graph[cur][v]!=float('inf') and minDist[cur]+graph[cur][v]<minDist[v]:
minDist[v]=minDist[cur]+graph[cur][v]
if minDist[n]!=float('inf'):
print(minDist[n])
else:
print(-1)
dijstra与prim算法的区别
prim是求 非访问节点到 最小生成树的最小距离,而 dijkstra是求 非访问节点到 源点的最小距离。
优化
在节点较多的情况下,效率较低,可以从边的角度出发,使用邻接表存储边和权值;在处理三部曲第一步的时候,不用遍历所有节点,直接把边(带权值)加入到小顶堆(利用堆来自动排序),每次从 堆顶里 取出 边 就是 距离源点最近的节点所在的边。
堆优化dijkstra代码
import heapq
class Edge:
def __init__(self, to, val):
self.to = to
self.val = val
class PriorityQueue:
def __init__(self):
self._queue = []
self._index = 0
def push(self, item):
heapq.heappush(self._queue, (item[1], self._index, item))
self._index += 1
def pop(self):
if self._queue:
return heapq.heappop(self._queue)[-1]
else:
raise Exception("pop from an empty priority queue")
def empty(self):
return not self._queue
def dijkstra(n, m, edges):
# 初始化网格
grid = [[] for _ in range(n + 1)]
# 添加边的权重到网格中
for p1, p2, val in edges:
grid[p1].append(Edge(p2, val))
# 初始化最小距离和是否访问过的列表
min_dist = [float('inf)] * (n + 1)
visited = [False] * (n + 1)
# 设置起点的初始距离为0
start = 1
min_dist[start] = 0
# 优先队列中存放 (节点, 源点到该节点的权值)
pq = PriorityQueue()
pq.push((start, 0))
while not pq.empty():
# 1. 第一步,选源点到哪个节点近且该节点未被访问过 (通过优先级队列来实现)
cur_node, cur_dist = pq.pop()
if visited[cur_node]:
continue
# 2. 第二步,该最近节点被标记访问过
visited[cur_node] = True
# 3. 第三步,更新非访问节点到源点的距离(即更新min_dist数组)
for edge in grid[cur_node]:
if not visited[edge.to] and min_dist[cur_node] + edge.val < min_dist[edge.to]:
min_dist[edge.to] = min_dist[cur_node] + edge.val
pq.push((edge.to, min_dist[edge.to]))
# 返回终点的最短距离
end = n
return min_dist[end] if min_dist[end] != float('inf) else -1
if __name__ == "__main__":
# 读取输入
n, m = map(int, input().split())
# 读取边
edges = [tuple(map(int, input().split())) for _ in range(m)]
# 计算并输出最短路径
shortest_path = dijkstra(n, m, edges)
print(shortest_path)
Bellman_ford算法
解决问题
单源最短路问题,本题 边的权值可以为负数(而dijkstra要求边的权值为正)
核心思想
对所有边进行松弛n-1次操作(n为节点数量),从而求得目标最短路
松弛的含义:如果 minDist[B] > minDist[A] + value
,则更新 minDist[B] = minDist[A] + value
n,m=map(int,input().split())
edges=[]
for _ in range(m):
v1,v2,val=map(int,input().split())
edges.append((v1,v2,val))
def bellman_ford(n,m,edges):
#初始化mindist数组,用于记录源点到其他点的最短距离
mindist=[float('inf')]*(n+1)
mindist[1]=0
#对所有边松弛n-1次
for _ in range(n-1):
for v1,v2,val in edges:
#松弛操作
if mindist[v1]!=float('inf') and mindist[v2]>mindist[v1]+val:
mindist[v2]=mindist[v1]+val
if mindist[n]!=float('inf'):
return mindist[n]
else:
return 'unconnected'
print(bellman_ford(n,m,edges))
拓展
(1)队列优化(SPFA)
对上一次松弛的时候更新过的节点作为出发节点所连接的边进行松弛就够了
class Edge:
def __init__(self, to, val):
self.to = to
self.val = val
def shortest_path(n, m, edges):
# 初始化最小距离和是否访问过的列表
min_dist = [float('inf')] * (n + 1)
min_dist[1] = 0 # 设置起点的初始距离为0
# 创建邻接表
grid = [[] for _ in range(n + 1)]
for p1, p2, val in edges:
grid[p1].append(Edge(p2, val))
# 使用队列来进行广度优先搜索
queue = deque([1]) # 起点加入队列
while queue:
current_node = queue.popleft()
for edge in grid[current_node]:
next_node = edge.to
weight = edge.val
if min_dist[next_node] > min_dist[current_node] + weight:
min_dist[next_node] = min_dist[current_node] + weight
queue.append(next_node)
# 返回终点的最短距离
end = n
return min_dist[end] if min_dist[end] != float('inf') else "unconnected"
(2)判断负权回路
在没有负权回路的图中,松弛 n 次以上 ,结果不会有变化;如果有负权回路,松弛 n 次,结果就会有变化了, 有负权回路 就可以无限最短路径(一直绕圈,就可以一直得到无限小的最短距离)
def bellman_ford(n, m, edges):
# 初始化最小距离和是否访问过的列表
min_dist = [float('inf')] * (n + 1)
min_dist[1] = 0 # 设置起点的初始距离为0
has_negative_cycle = False
# 对所有边 松弛 n-1 次
for _ in range(n - 1):
for p1, p2, val in edges:
# 松弛操作
if min_dist[p1] != float('inf') and min_dist[p2] > min_dist[p1] + val:
min_dist[p2] = min_dist[p1] + val
# 最后一次松弛判断是否存在负权回路
for p1, p2, val in edges:
if min_dist[p1] != float('inf') and min_dist[p2] > min_dist[p1] + val:
flag = True
break
if flag: return 'circle'
elif min_dist[n]==float('inf'): return 'unconnected'
else: return min_dist[n]
(3)单源有限最短路
思路:最多经过k个城市,即k+1条边相连的节点,对所有边松弛 k + 1次,就是求 起点到达 与起点k + 1条边相连的节点的 最短距离。由于存在负权回路,每次松弛都会更新所有节点,因此,在每次计算 minDist 时候,要基于 对所有边上一次松弛的 minDist 数值才行
def find_shortest_path(n, m, edges, src, dst, k):
# 初始化最小距离
min_dist = [float('inf')] * (n + 1)
min_dist[src] = 0
# 用于存储上一次迭代的结果
min_dist_copy = [0] * (n + 1)
# 对所有边 松弛 k+1 次
for i in range(1, k + 2):
min_dist_copy = min_dist.copy() # 获取上一次计算的结果
for p1, p2, val in edges:
# 松弛操作
if min_dist_copy[p1] != float('inf') and min_dist[p2] > min_dist_copy[p1] + val:
min_dist[p2] = min_dist_copy[p1] + val
# 返回终点的最短路径
if min_dist[dst] == float('inf'):
return "unreachable"
else:
return min_dist[dst]
Floyd算法
解决问题
多源最短路径(求多个起点到多个终点的多条最短路径),Fold算法对边的正负权值没有要求,适合稠密图且源点较多的情况。Fold算法实际是一个动态规划的问题,因此可以用动规五部曲
动规五部曲
(1)dp数组的含义:grid[i][j][k]=m,表示节点i到节点j以[1,...,k]集合为中间节点的最短距离为m
(2)递推公式:grid[i][j][k] = min( grid[i][k][k-1] + grid[k][j][k-1], grid[i][j][k-1])
情况1:节点i到节点j的最短路径经过节点k,即grid[i][j][k] = grid[i][k][k-1] + grid[k][j][k-1]
情况2:节点i到节点j的最短路径不经过节点k,即grid[i][j][k] = grid[i][j][k-1]
(3)初始化:k赋值为0,grid[i][j][0],grid数组其他元素初始化为最大值
(4)遍历顺序:三个for循环,分别遍历i,j和k,外层遍历k,内层遍历i或j
(5)举例推导dp数组
题目与代码
def main():
n, m = map(int, input().split())
# 初始化网格,使用三维列表来表示邻接矩阵
grid = [[[float('inf') for _ in range(n + 1)] for _ in range(n + 1)] for _ in range(n + 1)]
for _ in range(m):
p1, p2, val = map(int, input().split())
grid[p1][p2][0] = val
grid[p2][p1][0] = val # 因为是双向图
# 开始 Floyd 算法
for k in range(1, n + 1):
for i in range(1, n + 1):
for j in range(1, n + 1):
grid[i][j][k] = min(grid[i][j][k - 1], grid[i][k][k - 1] + grid[k][j][k - 1])
# 输出结果
z = int(input())
while z > 0:
start, end = map(int, input().split())
if grid[start][end][n] == float('inf'):
print(-1)
else:
print(grid[start][end][n])
z -= 1
if __name__ == "__main__":
main()
Astar算法(广搜改良版)
区别
在搜索最短路的时候, 如果是无权图(边的权值都是1) 则用广搜,如果是有权图(边有不同的权值),优先考虑 dijkstra。而Astar 关键在于 启发式函数, 也就是 影响 广搜或者 dijkstra 从 容器(队列)里取元素的优先顺序
启发式函数
影响队列内的元素排,需要给队列的每个节点权值,设每个阶段的权值为F,则F=G+H,G表示七点到达目前遍历节点的距离,F表示目前遍历的节点到达终点的距离
两点距离的计算方式
标签:图论,min,Python,graph,nextnode,随想录,range,visited,节点 From: https://blog.csdn.net/yyxm_1001/article/details/140419126