Data Structures Algorithms 简明教程
Map Colouring Algorithm
地图着色问题指出，在给定一个图 G {V, E}，其中 V 和 E 是该图的顶点和边集，V 中的所有顶点都需要用颜色着色，以便没有任何两个相邻顶点具有相同的颜色。
该算法的真实世界应用包括分配移动无线电频率、制定时间表、设计数独以及分配寄存器等等。
Map Colouring Algorithm
通过地图着色算法，一个图 G 和要添加到该图中的颜色被当做输入，并实现一个无相邻顶点具有相同颜色的着色图。
Algorithm
-
初始化图中所有顶点。
-
选择度最高的节点并为其着上任一颜色。
-
使用选择颜色函数选择用于图上的颜色，以便无相邻顶点具有相同颜色。
-
检查是否可以添加颜色，如果可以，将其添加到解集中。
-
从步骤 2 重复该过程，直至输出集准备完毕。
Examples
Step 1
找出所有顶点的度数 −
A – 4
B – 2
C – 2
D – 3
E – 3Step 2
选择度数最高的顶点首先着色，即 A，并使用选择颜色函数选择一种颜色。检查该颜色是否可以添加到顶点，如果可以，将其添加到解集中。
Step 3
从剩余顶点中选择度数次之的任何顶点，并使用选择颜色函数为其着色。
D 和 E 的度数次之均为 3，因此选择其中任何一个，比如说 D。
D 与 A 相邻，因此不能与 A 着成相同颜色。因此，请使用选择颜色函数选择不同的颜色。
Step 4
度数次之的顶点是 E，因此选择 E。
E 与 A 和 D 都相邻，因此不能着成与 A 和 D 相同的颜色。使用选择颜色函数选择不同的颜色。
Step 5
度数次之的顶点是 B 和 C。因此，随机选择其中任何一个。
B 同时与 A 和 E 相邻，因此不允许用 A 和 E 的颜色着色，但它不与 D 相邻，因此可以用 D 的颜色着色。
Step 6
剩下的是 C，它与 A 和 D 相邻，不允许使用 A 和 D 的颜色着色。但它不与 E 相邻，因此可以用 E 的颜色着色。
