一、哈密顿问题的历史

        哈密顿路径问题在上世纪七十年代初，终于被证明是“NP完全”的。据说具有这样性质的问题，难于找到一个有效的算法。实际上对于某些顶点数不到100的网络，利用现有最好的算法和计算机也需要比较荒唐的时间（比如几百年）才能确定其是否存在一条这样的路径。

二、哈密顿循环在图论的定义

        哈密顿回路的定义： G=(V,E)是一个图，若G中一条路径通过且仅通过每一个顶点一次，称这条路径为哈密顿路径。若G中一个回路通过且仅通过每一个顶点一次，称这个环为哈密顿回路。若一个图存在哈密顿回路，就称为哈密顿图。

三、深度优先遍历（Depth First Search, 简称 DFS）

        深度优先遍历主要思路是从图中一个未访问的顶点 V 开始，沿着一条路一直走到底，然后从这条路尽头的节点回退到上一个节点，再从另一条路开始走到底…，不断递归重复此过程，直到所有的顶点都遍历完成，它的特点是不撞南墙不回头，先走完一条路，再换一条路继续走。

        为了找到哈密顿循环，我们将使用回溯和 DFS 来遍历所有可能的不同类型的哈密顿路径。

• 我们首先创建一个路径列表，该列表将存储我们走过的当前路径
• 然后，我们从根开始一个 DFS，并在遍历图时不断附加我们得到的不同根。
• 我们用来查看一个节点在 DFS 中是否可以安全跳转的参数是：

     如果我们已经走过的路径中不存在节点。

     如果我们找到了一个哈密顿循环，那么我们就不需要再遍历了。

四、参考代码 

#------------------------------------------
'''
Defining our safe vertex as
something which is not in our
path
'''
def safeVertex(node):
    if(node in path):
        return False
    
    return True     
#-------------------------------------------
#-------------------------------------------
'''
Defining our DFS and 
Backtracking Logic
'''
def cycleDetection(E,n,root):
    path.append(root)
    #Seeing all the neigbours of the current root
    for i in E[root]:
        #Checking if our vertex satisfies the safe Vertex
        if(safeVertex(i)):
            #Checking if a cycle has already been detected or not in the
            #---------------------previous recursion--------------------
            if(cycleDetection(E,n,i)):
                return True
    
    #Checking if our current path has all the vertices
    if(len(path) == n):
        #If there is an edge from last vertex to the first vertex in our path
        #-------------then we have an hamiltonian cycle---------------------
        if(path[0] in E[path[len(path)-1]]):
            return True 
        else:
            return False
    #once we are done we remove that particle from the iteration
    path.pop()
#-------------------------------------------    
#-------------------------------------------
'''
Printing True or False
based on our output from Cycle Detection
'''
def HamiltonianCycle(E,n,root):
    if(cycleDetection(E,n,root)):
        print("True")
    else:
        print("False")
#-------------------------------------------
path = []
N_Vertices = int(input())
matrix = list()
for i in range(N_Vertices):
    matrix.append([])
N_Edges = int(input())
for j in range(N_Edges):
    edge_vertices = input().split()
    u = int(edge_vertices[0])
    v = int(edge_vertices[1])
    matrix[u-1].append(v-1)
    matrix[v-1].append(u-1)
    
HamiltonianCycle(matrix,N_Vertices,0)
#This path is actually a Hamiltonian cycle.
print(path)