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

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