GitHub | Crates.io | Docs.rs

此crate提供了解决图顶点着色问题的算法。这些算法返回一个"着色"，即每个顶点被分配到一个"颜色"（索引），使得没有两个同色的顶点通过边连接。这些算法使用启发式方法来最小化所需的不同颜色数量。

当前状态：基本功能正常，但未经过优化且测试不充分。

创建具有4个顶点、添加4条边并着色的示例。

use heuristic_graph_coloring::*;

let mut graph = VecVecGraph::new(4);
graph.add_edge(0, 1);
graph.add_edge(1, 2);
graph.add_edge(0, 2);
graph.add_edge(2, 3);
let coloring = color_greedy_by_degree(&graph);
assert_eq!(coloring, [1, 2, 0, 1]);

算法

如果你真的想要最少的颜色数，存在像回溯、SAT求解器或HEA进化方法这样的更慢的算法。上述算法仍然有助于提前确定上界。

另一方面，如果你想要更快，存在并行和分布式图着色算法。

测试

使用实例数据集（见instances/文件夹）和简单算法找到的颜色数作为难度度量，我们得到以下结果

请参阅完整结果data/instances.tsv。