path.py 文件源码

def hamiltonian_cycle(g: Graph, start: Vertex) -> List[Vertex]:
    path = [start]

    current = start

    visited: Set[Vertex] = set()

    try:
        while len(visited) != g.order:
            visited.add(current)

            (_, nearest) = min(
                (g.weight[current, v], v)
                for v in g.neighbors(current)
                if v not in visited
            )

            path.append(nearest)

            current = nearest
    except ValueError as e:
        if len(path) == g.order:
            return path

    raise HamiltonianCycleNotFound('graph has dead ends')