1、深度优先遍历（DFS）
2、广度优先遍历（BFS）
3、0-1BFS -- （2290. 到达角落需要移除障碍物的最小数目）
class Solution:
def minimumObstacles(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
dis = [[inf] * n for _ in range(m)]
dis[0][0], q = 0, deque([(0, 0)])
while q:
i, j = q.popleft()
for ni, nj in [(i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)]:
if not 0 <= ni < m: continue
if not 0 <= nj < n: continue
g = grid[ni][nj]
if dis[i][j] + g < dis[ni][nj]:
dis[ni][nj] = dis[i][j] + g
if g == 0: q.appendleft((ni, nj))
else: q.append((ni, nj))
return dis[-1][-1]
4、最短路径算法-迪杰斯特拉(Dijkstra)算法 （使用堆）-- （1514. 概率最大的路径）
class Solution:
def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start: int, end: int) -> float:
m = defaultdict(list)
for i, edge in enumerate(edges):
m[edge[0]].append((edge[1], succProb[i]))
m[edge[1]].append((edge[0], succProb[i]))
q = []
heappush(q, (-1, start))
v = set()
while q:
p, i = heappop(q)
if i == end: return -p
if i in v: continue
v.add(i)
for j, np in m[i]:
if j not in v:
heappush(q, (p * np, j))
return 0
5、并查集 -- （684. 冗余连接）
class Solution:
def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
res = []
parent = {}
def find(i):
if parent.get(i, i) != i:
parent[i] = find(parent[i])
return parent.get(i, i)
def union(i, j):
parent[find(i)] = find(j)
for edge in edges:
if find(edge[0]) == find(edge[1]):
return edge
else:
union(edge[0], edge[1])
return res
6、拓扑排序 -- （207. 课程表）
class Solution:
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
edges = collections.defaultdict(list)
indeg = [0] * numCourses
for info in prerequisites:
edges[info[1]].append(info[0])
indeg[info[0]] += 1
q = collections.deque([u for u in range(numCourses) if indeg[u] == 0])
visited = 0
while q:
visited += 1
u = q.popleft()
for v in edges[u]:
indeg[v] -= 1
if indeg[v] == 0:
q.append(v)
return visited == numCourses
8、欧拉回路 -- Hierholzer算法 -- （332. 重新安排行程）
class Solution:
def findItinerary(self, tickets: List[List[str]]) -> List[str]:
def dfs(curr: str):
while vec[curr]:
tmp = heapq.heappop(vec[curr])
dfs(tmp)
stack.append(curr)
vec = collections.defaultdict(list)
for depart, arrive in tickets:
vec[depart].append(arrive)
for key in vec:
heapq.heapify(vec[key])
stack = list()
dfs("JFK")
return stack[::-1]
9、最小生成树
（1）kruskal （基于边的算法，并查集 + 排序） -- （连接所有点的最小费用）
class Solution:
def minCostConnectPoints(self, points: List[List[int]]) -> int:
parent = {}
def find(a):
if parent.get(a, a) != a:
parent[a] = find(parent[a])
return parent.get(a, a)
def union(a, b):
parent[find(a)] = find(b)
get_dis = lambda x, y:abs(x[0] - y[0]) + abs(x[1] - y[1])
dis_arr = []
for i, x in enumerate(points):
for j in range(i + 1, len(points)):
y = points[j]
dis_arr.append((get_dis(x, y), i, j))
dis_arr.sort()
res, n = 0, 0
for dis, i, j in dis_arr:
if find(i) != find(j):
res += dis
n += 1
if n == len(points) - 1:
return res
union(i, j)
return res
（2）Prim算法 （基于顶点） -- （连接所有点的最小费用）
class Solution:
def minCostConnectPoints(self, points: List[List[int]]) -> int:
res, n = 0, len(points)
minHeap = []
MST = set()
heapq.heappush(minHeap, (0, tuple(points[0])))
while minHeap and len(MST) < n:
cost, x = heapq.heappop(minHeap)
if x in MST:
continue
MST.add(x)
res += cost
for y in points:
if tuple(y) not in MST:
heapq.heappush(minHeap, (abs(x[0] - y[0]) + abs(x[1] - y[1]), tuple(y)))
return res
10、连通性问题 -- tarjan算法 -- （1192. 查找集群内的关键连接）
class Solution:
def criticalConnections(self, n, connections):
ans, low, d = [], [-1] * n, [[] for _ in range(n)]
for i, j in connections:
d[i].append(j)
d[j].append(i)
def tarjan(c, v, p):
dfn = low[v] = c
for i in d[v]:
if i != p:
if low[i] == -1:
c += 1
tarjan(c, i, v)
if low[i] > dfn:
ans.append([v, i])
low[v] = min(low[v], low[i])
tarjan(0, 0, -1)
return ans
标签：基本,图论,return,parent,int,List,算法,find,def From： https://www.cnblogs.com/usaddew/p/17178009.html