假设有一个有向图由以下命名的顶点组成：
"ABC", "ABD", "ACB", "ACD", "ADB", "ADC", "BAC", "BAD",
"BCA", "BCD", "BDA", "BDC", "CAB", "CAD", "CBA", "CBD",
"CDA", "CDB", "DAB", "DAC", "DBA", "DBC", "DCA", "DCB"
这些是 4 个不同字母的 3 个字母排列。( total = 4*3*2=24) 顶点的名称也描述了它们之间的边。如果源的最后两个字符等于目标的前两个字符，则任何两个顶点相互连接，例如
A BC -> BC D
或者
D CB -> CB A
该图与 De Burjin 或 Kautz 的图非常相似，但并不相同。它是强连接的，我知道它有哈密顿循环。
为了解决这个问题，我不是算法专家，我只是浏览了最新的 boost 图形库并找到了枚举所有循环的 hawick_unique_circuits() 函数，这是我的示例代码：
#include <iostream>
#include <cstdint>
#include <vector>
#include <string>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/hawick_circuits.hpp>
#include "combination.hpp" // from http://howardhinnant.github.io/combinations.html
using namespace std;
using namespace boost;
typedef boost::adjacency_list<vecS, vecS, directedS, no_property, property<edge_weight_t, uint32_t> > TGraph;
TGraph m_Graph;
vector<string> m_StrVertexList;
void CreateStringVertexList(vector<string>& vl, uint32_t n, uint32_t k)
{
vl.clear();
if ((k > 0) && (n > k))
{
string code = "A";
while (--n)
{
code += code.back() + 1;
}
// for_each_permutation from Howard Hinnant
// http://howardhinnant.github.io/combinations.html
for_each_permutation(code.begin(), code.begin() + k, code.end(),
[&](string::iterator first, string::iterator last)->bool{ vl.push_back(string(first, last)); return(false); });
}
}
void AddEdgesFromStringVertex(TGraph& g, const vector<string>& vl)
{
uint32_t connection_len = vl.begin()->size() - 1;
g.clear();
for (uint32_t f = 0; f < vl.size(); f++)
for (uint32_t t = 0; t < vl.size(); t++)
{
if ((f != t) &&
(vl[f].substr(1, connection_len) == vl[t].substr(0, connection_len)))
{
add_edge(f, t, 1, g);
}
}
}
class hawick_visitor
{
public:
void cycle(const vector<TGraph::vertex_descriptor>& circuit, const TGraph& graph) const
{
if (circuit.size() == m_StrVertexList.size())
{
for (auto ii = circuit.begin(); ii != circuit.end(); ++ii)
{
cout << m_StrVertexList[*ii] << " -> ";
}
cout << endl;
}
}
};
void Circuits(const TGraph& g)
{
hawick_unique_circuits(g, hawick_visitor());
cout << "- end of hawick_unique_circuits() -" << endl;
}
void main(void)
{
//CreateStringVertexList(m_StrVertexList, 10, 4);
CreateStringVertexList(m_StrVertexList, 4, 3);
AddEdgesFromStringVertex(m_Graph, m_StrVertexList);
Circuits(m_Graph);
}
hawick_visitor 类只是检查找到的循环是否具有与 Graph 相同的顶点。如果有，这意味着我们找到了我们需要的哈密顿循环之一。
它适用于 24 个顶点，即从 4 个唯一字符中选择的 3 个字符，这是输出之一：
ABC -> BCA -> CAD -> ADB -> DBC -> BCD -> CDA -> DAC ->
ACB -> CBD -> BDC -> DCB -> CBA -> BAC -> ACD -> CDB ->
DBA -> BAD -> ADC -> DCA -> CAB -> ABD -> BDA -> DAB -> ABC
但是当我尝试解决类似的图形时，从 10 个唯一字符中选择了 5040 个名为 4 个字符的顶点，这个函数永远不会返回。应该有比 hawick_unique_circuits() 更好的算法来做到这一点。因为我知道有人在不到一分钟的时间内对 10,000 个顶点进行类似的计算，但我不知道怎么做。任何想法都受到高度赞赏。
这是该图有 5040 个我需要解决的顶点：
