python - Networkx 哈密顿循环

Question

我想在我的设计中添加汉密尔顿循环功能，但我不知道该怎么做。我知道有像 nx.is_tournament.hamiltonian_path 这样的算法等等，但我不知道如何准确地实现它们。下面是一个对我来说很好的欧拉循环的例子，我想以类似的方式创建一个汉密尔顿循环。

def isEulerian():
    isEulerian = nx.is_eulerian(myGlobalGraph)
    if isEulerian == True:
        trueInfo = 'this is Eulerian graph'
        trueInfo2 = '\n'
        Log.insert(INSERT, trueInfo)
        Log.insert(INSERT, trueInfo2)
        eulerianCircuit = list(nx.eulerian_circuit(myGlobalGraph))
        eulerianCircuitInfo = 'Order of action:'
        eulerianCircuitInfo2 = '\n'
        Log.insert(INSERT, eulerianCircuitInfo)
        Log.insert(INSERT, eulerianCircuitInfo2)
        for i in range(len(eulerianCircuit)):
            x = eulerianCircuit[i][::2]
            eulerianCircuitInfo3 = x
            eulerianCircuitInfo4 = ' > '
            Log.insert(INSERT, eulerianCircuitInfo3)
            Log.insert(INSERT, eulerianCircuitInfo4)
        eulerianCircuitInfo5 = '\n'
        Log.insert(INSERT, eulerianCircuitInfo5)
        eulerianCircuitInfo6 = '\n'
        Log.insert(INSERT, eulerianCircuitInfo6)
    elif isEulerian == False:
        falseInfo = 'this is not Eulerian graph'
        falseInfo2 = '\n'
        falseInfo3 = '\n'
        Log.insert(INSERT, falseInfo)
        Log.insert(INSERT, falseInfo2)
        Log.insert(INSERT, falseInfo3)

Answer 1

implementation您在 networkx 中所指的仅适用于锦标赛图，即每个节点之间只有一个有向边的图。我假设您需要一个通用的图形实现，因此它不适合您。
原因(我相信)这些不是 networkx 中哈密顿路径的实现，是找到一个的问题是 NP-Complete。因此，如果您只是创建一个蛮力算法，那将是您能做的最好的事情。
这是一个 brute force implementation我在github上找到的。