确定顶点列表是否为通过图形的路径

Question

给定一个图的输入和一个顶点列表，顶点列表是图中的路径吗？

G = [['a', 'b' , 'c' , 'd' , 'e' , 'f' , 'g' , 'h', 'i', 'j'],
     [({'a', 'b'}, 4), ({'a', 'c'}, 6), ({'a', 'd'}, 8), ({'b', 'e'}, 1) ,
      ({'b', 'f'}, 9), ({'c', 'f'}, 3), ({'d', 'g'}, 7), ({'d', 'h'}, 0) ,
      ({'e', 'i'}, 1), ({'e', 'j'}, 5), ({'g', 'h'}, 2), ({'i', 'j'}, 4)]]

L1 = ['a', 'd', 'h', 'g']

解决这个问题的最佳方法是什么？

编辑ː

这个问题现在已经解决了 - 在艾默里的帮助下ː

def edges(G):
    edgeset = [tuple(sorted(x[0])) for x in G[1]]
    return edgeset
def is_a_path(G,L,edgeset):
    for i in range(len(L)-1):
        a= tuple(sorted((L[i], L[i+1])))
        print(edgeset, a)
        if a not in edgeset:
            return False
    return True

Answer 1

注意：我假设G[0]是顶点列表，G[1]表示为({<vertex tag>, <vertex tag>}, <weight>)的(无向(边的列表。由于你使用集合来表示边，我假设你的图是无向的。

首先，您可能需要检查L1中的所有元素是否都是顶点。

for candidate in L1:
    if not (candidate in G[0]]):
        # If it's not a vertex, we exit returning False
        return False
# If we're here, it means every candidate was a vertex
return True

完成此操作后，您应该检查L1元素是否是路径，也就是说，对于L1的每个元素(最后一个元素除外(，存在该元素和下一个元素的边。

for i in range(len(L1)-1):
    # Create a candidate edge
    candidate = { L1[i], L1[i+1] }
    if not (candidate in G[0][:][0]):
        # If it's not in the list of edges, we exit returning False
        return False
# If every candidate edge is indeed an edge, then it's a path
return True