ocaml - Ocaml 图：用 bfs 着色图

Question

图着色（BFS）：给定一个图和一组“颜色”，是从 1 到 N 的整数，以相邻顶点分配不同颜色的方式为每个顶点分配一个整数

谁能帮我做这个项目？

Answer 1

当然。从一个顶点开始。选择一个未着色的顶点。将其添加到已处理顶点的列表中。如果它不大于 N，则使用与其邻居数量不同的最小数字对其进行着色。否则从列表中删除顶点，直到遇到无法分配颜色的顶点的邻居，然后擦除它们的颜色. 将最小的自由颜色分配给我们停止的顶点，它比以前的颜色高。继续。

ETA：虽然这是深度优先搜索，而不是广度优先搜索:-(我仍然认为 DFS 在图形着色方面比天真的 BFS 更好。