Graph Theory

图论

基本知识点：

• 顶点（Vertex）：图由一组顶点组成，每个顶点可以表示一个实体或对象。
• 边（Edge）：顶点之间的连接关系称为边。边可以是有向的（从一个顶点指向另一个顶点）或无向的（没有方向性）。
• 权重（Weight）：在有权图中，每条边可能会有一个与之关联的权重，用于表示顶点之间的距离、成本或其他度量。
• 度（Degree）：在无向图中，度就是每个节点相连的边的条数。对于有向图，分为入度（指向该顶点的边的数量）和出度（从该顶点出发的边的数量）。
• 邻接顶点（Adjacent Vertices）：对于一个顶点，与之直接相连的顶点称为邻接顶点。
• 路径（Path）：图中的路径是指由边连接的顶点序列。路径的长度是指路径上的边的数量。
• 环（Cycle）：如果路径的起点和终点是同一个顶点，并且没有重复的边，则称该路径为环。
• 连通图（Connected Graph）：在无向图中，如果任意两个顶点之间都存在路径，则该图被称为连通图。
• 强连通图（Strongly Connected Graph）：在有向图中，如果任意两个顶点之间都存在双向路径，则该图被称为强连通图。
• 最短路径（Shortest Path）：在带权图中，最短路径是指连接两个顶点之间权重和最小的路径。
• 图的表示方法：图可以使用邻接矩阵、邻接表等方式进行表示。邻接矩阵是一个二维矩阵，用于表示顶点之间的连接关系。邻接表是使用链表或数组表示每个顶点及其邻接顶点的列表。相比于邻接矩阵，邻接表需要的存储空间少，但是无法快速判断两个节点是否相邻。
• 最小生成树（Minimum Spanning Tree）：在带权无向图中，最小生成树是指连接图中所有顶点，并且边的权重和最小的树。
• 常见的图算法：常见的图算法包括深度优先搜索（DFS）、广度优先搜索（BFS）、Dijkstra算法（用于寻找最短路径）、拓扑排序、Prim算法和Kruskal算法（用于求最小生成树）等。
• 图的遍历代码：

  # 记录被遍历过的节点
  visited = []
  # 记录从起点到当前节点的路径，用于判断是否成环
  onPath = []
  
  """ 图遍历框架 """
  def traverse(graph, s):
      if visited[s]:
          return
      # 经过节点 s，标记为已遍历
      visited[s] = True
      # 做选择：标记节点 s 在路径上
      onPath[s] = True
      for neighbor in graph.neighbors(s):
          traverse(graph, neighbor)
      # 撤销选择：节点 s 离开路径
      onPath[s] = False

常见图算法

拓扑排序

拓扑排序（Topological Sorting）是一种对有向无环图（DAG）进行排序的算法。它可以找到一个满足所有依赖关系的顺序，使得对于图中的每一对有向边 (u, v)，顶点 u 都在顶点 v 之前。通俗说即把一幅图「拉平」，且这个「拉平」的图里面所有箭头方向都是一致的。如果一幅有向图中存在环是无法进行拓扑排序的，因为肯定做不到所有箭头方向一致；反过来，如果一幅图是「有向无环图」，那么一定可以进行拓扑排序。

• 基本思想：通过不断移除图中的入度为 0 的顶点，直到所有顶点都被处理完毕。
• 具体步骤：
  • 初始化：创建一个空的结果列表 result，以及一个队列 queue。
  • 计算顶点的入度：遍历有向图的所有顶点，计算每个顶点的入度（即指向该顶点的边的数量），并将入度为 0 的顶点加入队列 queue。
  • 拓扑排序：不断从队列中取出顶点，将其加入结果列表 result，并将其相邻顶点的入度减 1。如果减 1 后的入度为 0，将该顶点加入队列。
  • 输出结果：当队列为空时，所有顶点都已经被处理，并且按照拓扑排序的顺序加入了结果列表 result。将结果列表 result 返回作为拓扑排序的结果。
• 时间复杂度为 $O(V + E)$，其中 V 表示顶点的数量，E 表示边的数量。这是因为每个顶点和每条边都需要被访问一次。
• 代码：

  from collections import deque
  
  def topological_sort(graph):
      # 统计每个顶点的入度
      in_degree = {v: 0 for v in graph}
  
      # 计算每个顶点的入度
      for v in graph:
          for neighbor in graph[v]:
              in_degree[neighbor] += 1
  
      # 创建一个队列用于存储入度为0的顶点
      queue = deque([v for v in in_degree if in_degree[v] == 0])
  
      # 存储拓扑排序的结果
      result = []
  
      # 执行拓扑排序
      while queue:
          v = queue.popleft()
          result.append(v)
  
          # 将相邻顶点的入度减1，并将入度变为0的顶点加入队列
          for neighbor in graph[v]:
              in_degree[neighbor] -= 1
              if in_degree[neighbor] == 0:
                  queue.append(neighbor)
  
      # 如果图中存在环路，则无法进行拓扑排序
      if len(result) != len(graph):
          raise ValueError("The graph contains a cycle.")
  
      return result
  
  graph = {
      'A': ['B', 'C'],
      'B': ['D'],
      'C': ['D'],
      'D': ['E'],
      'E': []
  }
  
  result = topological_sort(graph)
  print(result)    # ['A', 'C', 'B', 'D', 'E']

二分图

二分图（Bipartite Graph），也称为二部图，是图论中一种特殊的图结构。

• 基本概念：二分图是指一个图可以将所有顶点分为两个不相交的顶点集合，且图中的每条边的两个端点分别属于不同的顶点集合。
• 判断：判断一个图是否为二分图有多种方法，其中最常用的方法是使用深度优先搜索（DFS）或广度优先搜索（BFS）进行染色。通过从任意一个顶点开始，将其染成一种颜色，然后按照染色规则继续染色相邻的顶点，如果在染色过程中发现相邻顶点已经染成了相同的颜色，则图不是二分图；如果染色完成后没有发现相邻顶点染成相同的颜色，则图是二分图。
• 应用：二分图可以用于建模和解决各种问题，例如匹配问题、调度问题、分配问题等。最大匹配问题可以在二分图上求解，而匈牙利算法是常用于解决最大匹配问题的算法之一。
• 代码：

  def is_bipartite(graph):
      # 定义三种颜色：0 表示未染色，1 表示染成红色，-1 表示染成蓝色
      colors = {}
  
      def dfs(node, color):
          colors[node] = color
          for neighbor in graph[node]:
              if neighbor not in colors:
                  if not dfs(neighbor, -color):
                      return False
              elif colors[neighbor] == color:
                  return False
          return True
  
      # 对每个顶点进行DFS染色判断
      for node in graph:
          if node not in colors:
              if not dfs(node, 1):
                  return False
  
      return True
  
  graph = {
      'A': ['B', 'C'],
      'B': ['A', 'D'],
      'C': ['A', 'D'],
      'D': ['B', 'C', 'E'],
      'E': ['D']
  }
  
  result = is_bipartite(graph)
  print(result)

并查集

并查集（Union-Find）算法是一个专门针对「动态连通性」的算法。

• 「连通」是一种等价关系，也就是说具有如下三个性质：
  1. 自反性：节点 p 和 p 是连通的。
  2. 对称性：如果节点 p 和 q 连通，那么 q 和 p 也连通。
  3. 传递性：如果节点 p 和 q 连通，q 和 r 连通，那么 p 和 r 也连通。
• UF时间复杂度：
  • find 主要功能就是从某个节点向上遍历到树根，其时间复杂度就是树的高度。我们可能习惯性地认为树的高度就是 logN，但这并不一定。logN 的高度只存在于平衡二叉树，对于一般的树可能出现极端不平衡的情况，使得「树」几乎退化成「链表」，树的高度最坏情况下可能变成 N。find, union, connected 的时间复杂度都是 O(N)。
  • 平衡性优化（按秩合并）+路径压缩：构造函数初始化数据结构需要 O(N) 的时间和空间复杂度；连通两个节点 union、判断两个节点的连通性 connected、计算连通分量 count 所需的时间复杂度均为 O(1)。
• 平衡性优化（按秩合并）+路径压缩：
  1. 用 parent 数组记录每个节点的父节点，相当于指向父节点的指针，所以 parent 数组内实际存储着一个森林（若干棵多叉树）。
  2. 用 size 数组记录着每棵树的重量，目的是让 union 后树依然拥有平衡性，保证各个 API 时间复杂度为 O(logN)，而不会退化成链表影响操作效率。
  3. 在 find 函数中进行路径压缩，保证任意树的高度保持在常数，使得各个 API 时间复杂度为 O(1)。使用了路径压缩之后，可以不使用 size 数组的平衡优化。
• tip：二维坐标映射到一维的常用技巧：二维坐标 (x,y) 可以转换成 x * n + y 这个数（m 是棋盘的行数，n 是棋盘的列数）
• 代码：

  class UF:
      # 连通分量个数
      count: int
      # 存储每个节点的父节点
      parent: List[int]
  
      # n 为图中节点的个数
      def __init__(self, n: int):
          self.count = n
          self.parent = [i for i in range(n)]  # 初始时，每个元素的父节点指向自身
          self.rank = [0] * size  # 记录每个集合的秩（树的高度）
  
      # 将节点 p 和节点 q 连通
      def union(self, p: int, q: int):
          rootP = self.find(p)
          rootQ = self.find(q)
  
          if rootP == rootQ:
              return
  
          # self.parent[rootQ] = rootP
          if rootP != rootQ:
              if self.rank[rootP] < self.rank[rootQ]:
                  self.parent[rootP] = rootQ
              elif self.rank[rootP] > self.rank[rootQ]:
                  self.parent[rootQ] = rootP
              else:
                  self.parent[rootQ] = rootP
                  self.rank[rootP] += 1
          # 两个连通分量合并成一个连通分量
          self.count -= 1
  
      # 判断节点 p 和节点 q 是否连通
      def connected(self, p: int, q: int) -> bool:
          rootP = self.find(p)
          rootQ = self.find(q)
          return rootP == rootQ
  
      def find(self, x: int) -> int:
          if self.parent[x] != x:   # 递归查找根节点，并进行路径压缩
              self.parent[x] = self.find(self.parent[x])
          return self.parent[x]
  
      # 返回图中的连通分量个数
      def count(self) -> int:
          return self.count
  
      '''
      fa = list(range(m * n))
      def find(x):
          if fa[x] != x:
              fa[x] = find(fa[x])
          return fa[x]
      
      def union((x, y), (i, j)):
          fa[find(x * n + y)] = fa[find(i * n + j)]
      '''

最小生成树

最小生成树（Minimum Spanning Tree，MST）算法是用于在连通加权图中找到一棵生成树，使得树上所有边的权重之和最小。生成树是原图的一个子图，它包含了所有的顶点和一部分边，且形成一个无环连通图。最小生成树算法主要有 Prim 算法（普里姆算法）和 Kruskal 算法（克鲁斯卡尔算法）两种，这两种算法虽然都运用了贪心思想。

• 贪心思路：将所有边按照权重从小到大排序，从权重最小的边开始遍历，如果这条边和最小生成树中的其它边不会形成环，则这条边是最小生成树的一部分，将它加入最小生成树集合；否则，这条边不是最小生成树的一部分，不要把它加入最小生成树集合。
• Prim 算法：Prim 算法是从一个起点的切分（一组横切边）开始执行类似 BFS 算法的逻辑，借助切分定理和优先级队列动态排序的特性，从这个起点「生长」出一棵最小生成树。它以贪心的方式选择边，每次选择与当前生成树连接的最小权重边所连接的顶点，并将该边加入生成树。Prim 算法可以使用优先队列来选择最小权重边，保证了边的选择是按照权重递增的顺序进行的。Prim 算法不需要事先对所有边排序，而是利用优先级队列动态实现排序的效果，Prim 算法类似于 Kruskal 的动态过程。每次切分都能找到最小生成树的一条边，然后又可以进行新一轮切分，直到找到最小生成树的所有边为止。
  • 复杂度分析：假设一幅图的节点个数为V，边的条数为E，首先需要O(E)的空间装所有边，而且 Union-Find 算法也需要O(V)的空间，所以 Kruskal 算法总的空间复杂度就是O(V + E)。时间复杂度主要耗费在排序，需要O(ElogE)的时间，Union-Find 算法所有操作的复杂度都是O(1)，套一个 for 循环也不过是O(E)，所以总的时间复杂度为O(ElogE)。
• Kruskal 算法：Kruskal 算法将图中的边按权重排序，然后从最小权重边开始逐步添加到生成树中。在添加边的过程中，需要确保不形成环路，即新添加的边与已有的边不构成环。Kruskal 算法使用并查集数据结构来判断边的两个顶点是否处于同一个连通分量，从而避免形成环路。
  • 时间复杂度：复杂度主要在优先级队列 pq 的操作上，由于 pq 里面装的是图中的「边」，假设一幅图边的条数为 E，那么最多操作 O(E) 次 pq。每次操作优先级队列的时间复杂度取决于队列中的元素个数，取最坏情况就是 O(logE)。所以总的时间复杂度为O(ElogE)。
• 代码：

  from heapq import heappop, heappush
  
  def prim(graph):
      n = len(graph)
      visited = [False] * n
      min_heap = []
      min_span_tree = []
  
      # 从顶点 0 开始构建最小生成树
      start_vertex = 0
      heappush(min_heap, (0, start_vertex))
  
      while min_heap:
          weight, vertex = heappop(min_heap)
          if visited[vertex]:
              continue
          visited[vertex] = True
  
          if weight != 0:
              min_span_tree.append((weight, vertex))
  
          for neighbor, edge_weight in graph[vertex]:
              if not visited[neighbor]:
                  heappush(min_heap, (edge_weight, neighbor))
  
      return min_span_tree
  
  
  def kruskal(graph):
      n = len(graph)
      disjoint_set = DisjointSet(n)
      min_span_tree = []
  
      # 将图中的边按权重排序
      edges = [(weight, u, v) for u in range(n) for v, weight in graph[u]]
      edges.sort()
  
      for weight, u, v in edges:
          if disjoint_set.find(u) != disjoint_set.find(v):
              disjoint_set.union(u, v)
              min_span_tree.append(weight)

最短路径算法

Floyd-Warshall

Floyd-Warshall 算法是一种用于求解所有顶点对之间（多源）最短路径的算法。它可以处理带有正权边或负权边的有向图或无向图，但不适用于存在负权环的情况。

• 基本思想：通过动态规划的方式逐步计算每对顶点之间的最短路径。它维护一个二维数组，称为距离矩阵，其中的元素 dist[u][v] 表示顶点 u 到顶点 v 的最短路径的长度。
• 基本步骤：
  1. 初始化：将距离矩阵的对角线元素设为 0，表示每个顶点到自身的距离为 0。对于有边相连的顶点，将距离矩阵的相应位置设为边的权重；对于没有边相连的顶点，将距离矩阵的相应位置设为无穷大。
  2. 迭代更新：对于每个顶点 k，依次考虑所有顶点对 (i, j) 的距离。如果通过顶点 k 可以获得更短的路径，则更新距离矩阵中的值 dist[i][j]。
  3. 返回结果：最终的距离矩阵就是所有顶点对之间的最短路径。
• 代码：

  INF = float('inf')
  
  def floyd_warshall(graph):
      n = len(graph)
      dist = [[INF] * n for _ in range(n)]
  
      # 初始化距离矩阵
      for u in range(n):
          for v, weight in graph[u]:
              dist[u][v] = weight
  
      # 迭代更新
      for k in range(n):
          for i in range(n):
              for j in range(n):
                  if dist[i][k] + dist[k][j] < dist[i][j]:
                      dist[i][j] = dist[i][k] + dist[k][j]
  
      return dist

Dijkstra

在 BFS 算法框架详解 用的是普通的队列 Queue 来遍历多叉树，而对于加权图的最短路径来说，得用优先级队列 PriorityQueue自动排序的特性，将路径权重较小的节点排在队列前面，以此为基础施展 BFS 算法，也就变成了 Dijkstra 算法。

Dijkstra 算法是一种用于解决带有非负权边的单源最短路径问题的算法。它能够找到从起点到图中所有其他顶点的最短路径。

• 基本思想：通过逐步松弛顶点来逐步确定最短路径。它维护一个距离数组，记录从起点到每个顶点的最短路径估计值。算法的迭代过程中，每次选择距离数组中值最小的顶点，并对其邻接顶点进行松弛操作，更新距离数组中的值。通过不断选择最短路径估计值最小的顶点，最终可以确定起点到其他所有顶点的最短路径。Dijkstra 可以理解成一个带 dp table（或者说备忘录）的 BFS 算法。
• 算法条件：加权有向图，没有负权重边
• 基本步骤：
  1. 初始化：将起点的距离设为 0，其余顶点的距离设为无穷大。
  2. 迭代更新：重复以下步骤，直到所有顶点都被处理或者没有可选顶点为止：选择距离数组中值最小的顶点作为当前顶点；对当前顶点的邻接顶点进行松弛操作，更新距离数组中的值。
  3. 返回结果：最终的距离数组就是起点到所有顶点的最短路径。
• 时间复杂度： O(ElogV)，其中 E 代表图中边的条数，V 代表图中节点的个数。因为理想情况下优先级队列中最多装 V 个节点，对优先级队列的操作次数和 E 成正比，所以整体的时间复杂度就是 O(ElogV)。
• 代码：

  import heapq
  
  INF = float('inf')
  
  def dijkstra(graph, start):
      n = len(graph)
      distance = [INF] * n
      distance[start] = 0
  
      min_heap = [(0, start)]
  
      while min_heap:
          dist, u = heapq.heappop(min_heap)
  
          # 如果当前顶点已经处理过，则跳过
          if dist > distance[u]:
              continue
  
          for v, weight in graph[u]:
              new_dist = distance[u] + weight
  
              # 如果找到了更短的路径，则更新距离数组和堆中的值
              if new_dist < distance[v]:
                  distance[v] = new_dist
                  heapq.heappush(min_heap, (new_dist, v))
  
      return distance

Bellman-Ford

Bellman-Ford 算法是一种用于解决带有负权边的单源最短路径问题的算法。它可以应对图中存在负权边和负权环的情况。

• 基本思想：通过逐步松弛边的权重来逐步逼近最短路径。它维护一个距离数组，记录从起点到每个顶点的最短路径估计值。算法的迭代过程中，通过对每条边进行松弛操作，不断更新距离数组中的值，直到无法再进行松弛为止。
• 基本步骤：
  1. 初始化：将起点的距离设为 0，其余顶点的距离设为无穷大。
  2. 迭代更新：对于图中的每条边，逐步松弛边的权重。对于边 (u, v) 来说，如果从起点到顶点 u 的路径经过边 (u, v) 能够获得更短的路径，则更新顶点 v 的距离值。
  3. 检测负权环：在迭代更新的过程中，如果存在顶点的距离值发生变化，则说明图中存在负权环。由于负权环可以无限次地减小路径的长度，因此 Bellman-Ford 算法可以通过检测负权环来判断是否存在无限小的最短路径。
  4. 返回结果：如果不存在负权环，则最终的距离数组就是起点到所有顶点的最短路径。
• 时间复杂度：O(V * E)，其中 V 是顶点的数量，E 是边的数量。
• 代码：

  INF = float('inf')
  
  def bellman_ford(graph, start):
      n = len(graph)
      distance = [INF] * n
      distance[start] = 0
      predecessor = [-1] * n
  
      for _ in range(n - 1):
          for u in range(n):
              for v, weight in graph[u]:
                  if distance[u] != INF and distance[u] + weight < distance[v]:
                      distance[v] = distance[u] + weight
                      predecessor[v] = u
  
      # 检测负权环
      for u in range(n):
          for v, weight in graph[u]:
              if distance[u] != INF and distance[u] + weight < distance[v]:
                  raise ValueError("Graph contains a negative weight cycle.")
  
      # # Check for negative-weight cycles，并记录环路径negative_cycle
      # negative_cycle = None
      # for u in range(n):
      #     for v, weight in graph[u]:
      #         if distance[u] + weight < distance[v]:
      #             # Negative-weight cycle found
      #             negative_cycle = []
      #             cycle_vertex = v
      #             while cycle_vertex not in negative_cycle:
      #                 negative_cycle.append(cycle_vertex)
      #                 cycle_vertex = predecessor[cycle_vertex]
      #             negative_cycle.append(cycle_vertex)
      #             negative_cycle.reverse()
      #             break
      #     if negative_cycle is not None:
      #         break
  
      return distance
  
  graph = [
      [(1, 4), (2, 2)],
      [(3, 3)],
      [(1, 1), (3, -5)],
      [(4, 2)],
      []
  ]
  
  start_vertex = 0
  distances = bellman_ford(graph, start_vertex)
  print(distances)

SPFA

SPFA（Shortest Path Faster Algorithm）是一种用于求解带有负权边的单源最短路径问题的算法。它是对 Bellman-Ford 算法的一种优化，通过使用队列进行松弛操作的选择，减少了不必要的重复操作，从而提高了算法的效率。

• 基本步骤：

1. 初始化：将起点的距离设为 0，其余顶点的距离设为无穷大。将起点加入队列中。
2. 迭代更新：从队列中取出一个顶点，并对其邻接顶点进行松弛操作。如果通过当前顶点 u 可以获得更短的路径，则更新邻接顶点 v 的距离值，并将 v 加入队列中（如果 v 不在队列中）。继续迭代，直到队列为空。
3. 检测负权环：通过统计每个顶点的入队次数来实现的。如果某个顶点入队的次数超过图中顶点的数量，即超过了 n 次（n 是顶点的数量），则说明存在负权环。
4. 返回结果：如果不存在负权环，则最终的距离数组就是起点到所有顶点的最短路径。

• 时间复杂度：一般情况下的时间复杂度是 O(kE)，其中 k 是松弛操作的次数，E 是边的数量。在大多数情况下，SPFA 算法的运行时间要比 Bellman-Ford 算法更快。
• 代码：

  from collections import deque
  
  INF = float('inf')
  
  def spfa(graph, start):
      n = len(graph)
      distance = [INF] * n
      distance[start] = 0
  
      queue = deque()
      queue.append(start)
  
      # 记录每个顶点入队的次数。如果某个顶点的入队次数超过 n 次，则直接返回 "存在负权环"。
      count = [0] * n
      count[start] = 1
  
      while queue:
          u = queue.popleft()
  
          for v, weight in graph[u]:
              new_dist = distance[u] + weight
  
              if new_dist < distance[v]:
                  distance[v] = new_dist
  
                  if v not in queue:
                      queue.append(v)
                      count[v] += 1
  
                      # 检测负权环
                      if count[v] > n:
                          return "存在负权环"
  
      return distance

A*算法

A*算法是一种启发式搜索算法，用于在图形表示的问题中找到最短路径或最优解。它结合了Dijkstra算法的广度优先搜索和贪心算法的启发式评估，以在搜索过程中更快地找到目标。

• 基本思想：通过维护一个开放列表和一个关闭列表来搜索图形中的节点。开放列表存储待扩展的节点，而关闭列表存储已经访问过的节点。在每一步中，A算法根据节点的启发式评估值选择最有希望的节点进行扩展。这个启发式评估值通常是一个估计值，用于预测从当前节点到目标节点的最短路径代价。
• 基本步骤：
  1. 将起点加入开放列表，并设置起点的启发式评估值（例如，预估的从起点到目标节点的最短路径代价）。
  2. 重复以下步骤直到找到目标节点或开放列表为空：从开放列表中选择启发式评估值最低的节点作为当前节点。将当前节点从开放列表中移除，并将其加入关闭列表。如果当前节点是目标节点，搜索结束，找到了最短路径或最优解。否则，对当前节点的所有邻接节点进行如下操作：如果邻接节点已经在关闭列表中，则跳过该节点。如果邻接节点不在开放列表中，将其加入开放列表，并计算它的启发式评估值。如果邻接节点已经在开放列表中，更新其启发式评估值为更低的值（如果需要）。
  3. 如果开放列表为空，表示无法到达目标节点，搜索结束。
• 注意：A算法的效率和搜索结果的质量高度依赖于所选择的启发式评估函数。一个合理的启发式评估函数能够提供较为准确的路径代价估计，从而指导搜索过程朝着最有希望的方向前进。但如果启发式评估函数不准确或不适当，可能会导致搜索结果不是最优解或搜索效率较低。因此，在使用A算法时，选择和设计合适的启发式评估函数非常重要。
• 代码：

  import heapq
  
  def heuristic(node, goal):
      # 启发式评估函数，计算当前节点到目标节点的估计代价
      return abs(node[0] - goal[0]) + abs(node[1] - goal[1])
  
  def astar(graph, start, goal):
      # 初始化数据结构
      open_list = []
      closed_set = set()
      came_from = {}
      g_score = {start: 0}
      f_score = {start: heuristic(start, goal)}
  
      # 将起点加入开放列表
      heapq.heappush(open_list, (f_score[start], start))
  
      while open_list:
          current = heapq.heappop(open_list)[1]
  
          if current == goal:
              # 找到目标节点，构建路径并返回
              path = []
              while current in came_from:
                  path.append(current)
                  current = came_from[current]
              path.append(start)
              return path[::-1]
  
          closed_set.add(current)
  
          for neighbor in graph[current]:
              if neighbor in closed_set:
                  continue
  
              # 计算当前节点到邻接节点的实际代价
              tentative_g_score = g_score[current] + 1
  
              if neighbor not in open_list:
                  open_list.append((f_score.get(neighbor, float('inf')), neighbor))
              elif tentative_g_score >= g_score.get(neighbor, float('inf')):
                  continue
  
              came_from[neighbor] = current
              g_score[neighbor] = tentative_g_score
              f_score[neighbor] = tentative_g_score + heuristic(neighbor, goal)
  
      # 开放列表为空，无法到达目标节点
      return None
  
  # 示例使用
  graph = {
      (0, 0): [(0, 1), (1, 0)],
      (0, 1): [(0, 0), (1, 1)],
      (1, 0): [(0, 0), (1, 1), (2, 0)],
      (1, 1): [(0, 1), (1, 0), (2, 1)],
      (2, 0): [(1, 0), (2, 1)],
      (2, 1): [(1, 1), (2, 0)]
  }
  
  start = (0, 0)
  goal = (2, 1)
  
  path = astar(graph, start, goal)
  if path:
      print("找到最短路径：", path)
  else:
      print("无法到达目标节点")

力扣指南

图论
题目	技巧	难度
✅797. 所有可能的路径	经典回溯	🌟🌟
✅207. 课程表		🌟🌟
✅210. 课程表 II	拓扑排序	🌟🌟
✅785. 判断二分图		🌟
✅886. 可能的二分法		🌟🌟
✅130. 被围绕的区域	并查集	🌟🌟
✅1334. 阈值距离内邻居最少的城市	Floyd	🌟🌟
✅2976. 转换字符串的最小成本 I	Floyd	🌟🌟
✅990. 等式方程的可满足性	Kruskal 算法	🌟🌟
✅1584. 连接所有点的最小费用	Kruskal + prim	🌟🌟
✅743. 网络延迟时间	标准dijkstra	🌟🌟
✅1631. 最小体力消耗路径	从上下左右都更新时用图	🌟🌟
✅1514. 概率最大的路径	无向图是双向图	🌟🌟
✅997. 找到小镇的法官	计算出入度	🌟
✅787. K 站中转内最便宜的航班	dijkstra、DP	🌟🌟