我正在接受输入，例如 4 1 3 1 2 2 4
第一行是节点数，之后的行是边。我必须尝试为图表着色，如果不能，我需要在图表中列出导致错误的循环。
到目前为止这很好，除了其中一张图包含 1,000,000 个节点。每次我尝试使用它时，都会出现 Stack Overflow 错误，即使我对其进行了更多简化，并将 eclipse 的最大堆大小提高到 1024m。
我不是要代码，只是问我是否在做一些公然错误的事情以不断出错。
NickT
问问题
1026 次
3 回答
1
如果它是一个二分图，您总是可以只用两种颜色对其进行着色（例如，将第一个分区着色为白色，将第二个分区着色为黑色）。
通常当一个人考虑为图表着色时，他应该指定颜色的数量。您始终可以通过为每个节点分配不同的颜色来为图形着色。另一个例子：对于平面图，只需要四种颜色。然而，对于大多数图来说，图的 [色数] 是 [NP]。
[NP] http://en.wikipedia.org/wiki/Karp%27s_21_NP-complete_problems
于 2009-05-09T08:02:42.107 回答
1
也许你可以优化你的周期检测算法。这可能对您有所帮助：http ://en.wikipedia.org/wiki/Cycle_detection
除此之外，一百万个节点加上邻接矩阵可能一次处理太多了，所以也许有一种方法可以一次只加载图的一部分。
于 2009-05-05T14:42:43.047 回答
-1
嗯，这是一个 NP 完全问题（最长周期），所以这种事情很可能会发生。
我可能会再次碰撞堆，然后让它运行......
编辑：没关系。让我的减少倒退。
于 2009-05-05T14:33:54.953 回答