回溯算法----着色问题

给定无向连通图G和m种颜色，用这些颜色给图的顶点着色，每个顶点一种颜色。如果要求G的每条边的两个顶点着不同颜色。给出所有可能的着色方案

回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。

图的结构类型: 构建一个图的结构体用一个数组存储图的顶点,每个顶点结构体会有一个指向相同类型的指针,指向与顶点相连的边, 指针中还会有指针,也指向与顶点相连的边,直到没有

回溯算法----着色问题

算法:

只使用数组中的头顶点,头顶点后面,与该顶点相连的顶点用来判断,该顶点能否用这种颜色, 用一个全局数组表示某顶点的颜色

每个顶点都可以涂上各种颜色,当一个涂上某种颜色后,指向数组的下一个顶点,也可以涂上各种颜色,但当该顶点与之前涂过颜色的顶点有边相连时,颜色不能一样,如果遇到这种情况,就放弃这种方案,回溯返回.

当遍历完数组(顶点都涂完了颜色),就输出当前方案

回溯算法----着色问题

时间复杂度:(顶点数 * 颜色^顶点数);