输入：一个具有n顶点的连通无向图G。
输出：顶点0, 1, ..., n - 1的线性排序，使最小化
sum(j - i for i in range(n) for j in range(n) if i < j and (i, j) in G)。
n可以是大约1000000，并且边缘的数量将是大于n的恒定因子，大约5000000。在稍微更一般的问题中，边可能具有小的正整数权重。精确的解决方案是优选的，但不是必须的。
一种方法可能是泡沫式的变体，如果它能降低总和，就可以互换要素。但我不确定这个算法是否会陷入局部极小值。
您的任务似乎是最小线性分配问题。网上有一篇关于这个主题的博士论文(Seitz，Hanna-对最小线性布置问题(，有一个可访问的阐述(见第27页及其后(。
这个问题是NP难题。引用的资源报告了最著名的算法O(|E| * 2^|V|)的复杂性(第29页及其后(。它还列出了已知有效(多项式(算法的图类，并讨论了近似方案。
PS：
这里不是专家，只是遇到了这个问题和论文，这似乎是一个很好的起点。