Tra*_*man 2 c++ graph hamiltonian-cycle
首先是一些定义:
定义1
如果对于每对非相邻顶点u和v,则d =(V,E)被称为"密集",d(u)+ d(v)> = n其中n = | V | 和d(*)表示顶点的程度*
定义2
G上的"哈密顿循环"是一个顶点序列(vi1,vi2,...... vin,vi1),所有l!= h的vil!= vih和{vil,vil}是G的边缘.
问题是:编写一个程序,给定一个密集的无向图G =(V; E)作为输入,确定G是否允许G上的哈密顿循环并输出该循环(如果有),或输出"N"如果没有.
我的解决方案是找到从源开始的所有可能路径,并检查是否存在返回此源的路径.不幸的是,这种解决方案效率不高.
有什么建议？谢谢.