算法模板，最科学的刷题方式，最快速的刷题路径，一个月从入门到 offer，你值得拥有 🐶~

算法模板顾名思义就是刷题的套路模板，掌握了刷题模板之后，刷题也变得好玩起来了~

[最短路径](./shortest_path.md)

[图的表示](./graph_representation.md)

for dr, dcin neighors:

nr, nc= r+ dr, c+ dc

if0<= nr< Mand0<= nc< N:

if A[nr][nc]==0:# meet and edge

if A[nr][nc]==0:

A[nr][nc]=-2

bfs.append((nr, nc))

elif A[nr][nc]==1:

最小危险值为最小生成树中 0 到 n 路径上的最大边权。

最小危险值为最小生成树中 0 到 n 路径上的最大边权。以此题为例给出最小生成树的两种经典算法。

- 算法 1:[Kruskal's algorithm]([https://en.wikipedia.org/wiki/Kruskal%27s_algorithm](https://en.wikipedia.org/wiki/Kruskal's_algorithm))，使用[并查集](../../data_structure/union_find.md)实现。

parent=list(range(N+1))

rank= [1]* (N+1)

deffind(x):

if parent[parent[x]]!= parent[x]:

defunion(x,y):

px, py= find(x), find(y)

if px!= py:

if px== py:

if rank[px]> rank[py]:

parent[py]= px

elif rank[px]< rank[py]:

parent[px]= py

else:

parent[px]= py

rank[py]+=1

edges=sorted(zip(W, X, Y))

return w

- 算法 2:[Prim's algorithm]([https://en.wikipedia.org/wiki/Prim%27s_algorithm](https://en.wikipedia.org/wiki/Prim's_algorithm))，使用[优先级队列 (堆)](../../data_structure/heap.md)实现

classSolution:

for dr, dcin neighors:

nr, nc= r+ dr, c+ dc

if0<= nr< Mand0<= nc< N:

if A[nr][nc]==0:# meet and edge

if A[nr][nc]==0:

A[nr][nc]=-2

bfs.append((nr, nc))

elif A[nr][nc]==1:

return flip

flip+=1

用于求解单源最短路径问题。思想是 greedy 构造 shortest path tree (SPT)，每次将当前距离源点最短的不在 SPT 中的结点加入SPT，与构造最小生成树 (MST) 的 Prim's algorithm 非常相似。可以用 priority queue (heap) 实现。

标准的单源最短路径问题，使用朴素的的 Dijikstra 算法即可，可以当成模板使用。

classSolution:

defnetworkDelayTime(self,times: List[List[int]],N:int,K:int) ->int:

graph_neighbor= collections.defaultdict(list)

for s, e, tin times:

graph_neighbor[s].append((e, t))

SPT= {}

min_heap= [(0, K)]

while min_heap:

delay, node= heapq.heappop(min_heap)

if nodenotinSPT:

SPT[node]= delay

for n, din graph_neighbor[node]:

if nnotinSPT:

heapq.heappush(min_heap, (d+ delay, n))

returnmax(SPT.values())iflen(SPT)== Nelse-1

在标准的单源最短路径问题上限制了路径的边数，因此需要同时维护当前 SPT 内每个结点最短路径的边数，当遇到边数更小的路径 (边权和可以更大) 时结点需要重新入堆，以更新后继在边数上限内没达到的结点。

classSolution:

deffindCheapestPrice(self,n:int,flights: List[List[int]],src:int,dst:int,K:int) ->int:

graph_neighbor= collections.defaultdict(list)

for s, e, pin flights:

graph_neighbor[s].append((e, p))

prices, steps= {}, {}

min_heap= [(0,0, src)]

whilelen(min_heap)>0:

price, step, node= heapq.heappop(min_heap)

if node== dst:# early return

return price

if nodenotin prices:

prices[node]= price

steps[node]= step

if step<= K:

step+=1

for n, pin graph_neighbor[node]:

if nnotin pricesor step< steps[n]:

heapq.heappush(min_heap, (p+ price, step, n))

当求点对点的最短路径时，BFS遍历结点数目随路径长度呈指数增长，为缩小遍历结点数目可以考虑从起点 BFS 的同时从终点也做 BFS，当路径相遇时得到最短路径。

用于求解单源最短路径问题。思想是 greedy 构造 shortest path tree (SPT)，每次将当前距离源点最短的不在 SPT 中的结点加入SPT，与构造最小生成树 (MST) 的 Prim's algorithm 非常相似。可以用 priority queue (heap) 实现。

标准的单源最短路径问题，使用朴素的的 Dijikstra 算法即可，可以当成模板使用。

classSolution:

defnetworkDelayTime(self,times: List[List[int]],N:int,K:int) ->int:

graph_neighbor= collections.defaultdict(list)

for s, e, tin times:

graph_neighbor[s].append((e, t))

SPT= {}

min_heap= [(0, K)]

while min_heap:

delay, node= heapq.heappop(min_heap)

if nodenotinSPT:

SPT[node]= delay

for n, din graph_neighbor[node]:

if nnotinSPT:

heapq.heappush(min_heap, (d+ delay, n))

returnmax(SPT.values())iflen(SPT)== Nelse-1

在标准的单源最短路径问题上限制了路径的边数，因此需要同时维护当前 SPT 内每个结点最短路径的边数，当遇到边数更小的路径 (边权和可以更大) 时结点需要重新入堆，以更新后继在边数上限内没达到的结点。

classSolution:

deffindCheapestPrice(self,n:int,flights: List[List[int]],src:int,dst:int,K:int) ->int:

graph_neighbor= collections.defaultdict(list)

for s, e, pin flights:

graph_neighbor[s].append((e, p))

prices, steps= {}, {}

min_heap= [(0,0, src)]

whilelen(min_heap)>0:

price, step, node= heapq.heappop(min_heap)

if node== dst:# early return

return price

if nodenotin prices:

prices[node]= price

steps[node]= step

if step<= K:

step+=1

for n, pin graph_neighbor[node]:

if nnotin pricesor step< steps[n]:

heapq.heappush(min_heap, (p+ price, step, n))

当需要求解有目标的最短路径问题时，BFS 或 Dijkstra's algorithm 可能会搜索过多冗余的其他目标从而降低搜索效率，此时可以考虑使用 A* algorithm。原理不展开，有兴趣可以自行搜索。实现上和 Dijkstra’s algorithm 非常相似，只是优先级需要加上一个到目标点距离的估值，这个估值严格小于等于真正的最短距离时保证得到最优解。当 A* algorithm 中的距离估值为 0 时 退化为 BFS 或 Dijkstra’s algorithm。

思路 1：BFS。为了方便对比 A* 算法写成了与其相似的形式。

- 方法 1：BFS。为了方便对比 A* 算法写成了与其相似的形式。

classSolution:

思路 2：A* algorithm

- 方法 2：A* algorithm

classSolution:

非常经典的拓扑排序应用题目。下面给出 3 种实现方法，可以当做模板使用。

非常经典的拓扑排序应用。下面给出 3 种实现方法，可以当做模板使用。

- 方法 1：DFS 的递归实现

return tsort_rev[::-1]

- 方法 2：DFS 的迭代实现

return tsort_rev[::-1]

- 方法 3：[Kahn's algorithm](https://en.wikipedia.org/wiki/Topological_sorting#Kahn's_algorithm)

classSolution:

deffindOrder(self,numCourses:int,prerequisites: List[List[int]]) -> List[int]: