题目4图着色问题

       给定一个无向图G=（V，E），其中V为顶点集合，E为边集合，图着色问题即为将V分为K个颜色组，每个组形成一个独立集，即其中没有相邻的顶点。器优化版本是希望获得最小的K值。

解题思路

本题与前几道题相比最大的不同点是，待分配的对象是可变的，如果是给出固定的颜色种类和一个无向图，球有多少种着色方法时，那就完全和n皇后问题是一种思想了，连数据结构都可以说是一模一样，但是这题求的是最少使用的颜色总数，可以定义一个sum来存放完成一次深度搜索时求得的使用的颜色总数，用mins来记录最小的颜色数。求每个点的颜色时，先用已有的每个颜色来试探，有符合条件的颜色时，sum就不用加一，记录此时sum的值便于回溯，然后递归调用函数求下一个点的颜色，但是如果已有的所有颜色都试探失败，这个时候sum就需要加一。在递归出口比较每次求得的总颜色数，每次都取最小的，进而求出最小的颜色数。