首先，咱们得先明确无向图中路径的核心定义：一个顶点序列能被称为路径，当且仅当序列里每一对相邻的顶点，在图中都存在一条直接相连的边（毕竟这是无向图，边是无序的，比如{'a','d'}和{'d','a'}算同一条边）。

针对你给出的图G和顶点列表L1 = ['a', 'd', 'h', 'g']，最优的验证方法可以分成这几步来做，简单又高效：

第一步：预处理图的边，构建快速查询结构 #

如果每次检查相邻顶点都要遍历所有边，效率会很低（时间复杂度O(E)）。所以我们可以先把图的边转换成邻接表或者哈希集合，这样查询两个顶点是否相邻的时间能降到O(1)。

举个Python实现的例子，用邻接表的方式：

# 从给定的图G里拆分出顶点集合和边集合
vertices, edges = G
# 初始化邻接表：每个顶点对应一个邻接顶点的集合
adjacency_dict = {v: set() for v in vertices}
# 遍历所有边，填充邻接表
for edge, _ in edges:
    u, v = tuple(edge)
    adjacency_dict[u].add(v)
    adjacency_dict[v].add(u)

或者更直接的，把所有边转换成排序后的元组集合（这样能统一无向边的顺序）：

edge_set = set()
for edge, _ in edges:
    # 把无序集合转成排序后的元组，确保('a','d')和('d','a')是同一个元素
    sorted_edge = tuple(sorted(edge))
    edge_set.add(sorted_edge)

第二步：遍历顶点列表，逐一验证相邻顶点对 #

有了快速查询的结构后，只需要遍历L1里的每一组相邻顶点，检查它们是否在图中有直接相连的边：

• 从列表的第一个顶点开始，依次取L1[i]和L1[i+1]（i从0到len(L1)-2）
• 用预处理好的结构查询这对顶点是否存在边
• 如果所有相邻顶点对都有对应的边，那这个列表就是图的路径；只要有一对没有，就不是路径

针对你的L1具体验证：

• a和d：图里有边({'a','d'},8)，存在
• d和h：图里有边({'d','h'},0)，存在
• h和g：图里有边({'g','h'},2)，存在
  所以L1确实是图中的一条路径。

为什么这是最优方法？ #

• 时间复杂度最优：预处理边的时间是O(E)，遍历顶点列表的时间是O(k)（k是列表长度），整体复杂度是O(E + k)——这已经是理论上的最优了，因为你至少得遍历所有边来构建查询结构，也得遍历所有顶点对来验证。
• 实现简单直观：不管是邻接表还是边集合，代码写起来都很简洁，不容易出错。
• 复用性强：如果之后要验证更多顶点列表，预处理好的结构可以重复使用，不用每次都重新遍历所有边。

内容的提问来源于stack exchange，提问作者user9713961