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

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']

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

编辑ː

在 Aimery 的帮助下，现在已经解决了这个问题ː

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 的每个元素（除了最后一个），都存在一条边 this元素和下一个。

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

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

determine whether a list of vertices is a path through a graph

graph-theory

vertices

python-3.x