网络X哈密顿回路

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)

- Abso

Answer 1

您所提到的networkx中的实现仅适用于锦标赛图，这些图是指每个节点之间恰好有一条有向边的图。我猜您需要一个通用的图实现，因此它对您来说不合适。

我认为没有在networkx中实现汉密尔顿路径的原因是，找到这样一条路径的问题是NP完全问题。因此，如果您只是创建一个蛮力算法，那么这将是您能做的最好的算法。

这里是我在github上找到的一个蛮力实现。

- Yonlif

---

请注意，Gist 找到的是哈密顿路径，而不是哈密顿循环。 - DiddiZ