图着色问题可以分为两种：

1、判定m中颜色是否可以为一个图的每个顶点进行着色，使得相邻（之间右边）的两个顶点颜色不能相同，这类图着色问题称作判定图着色。

2、给定一个图，对它的顶点进行着色，使得相邻的两个顶点颜色不能相同，求最少可以用几种颜色对图进行着色，并满足要求。

 

1、第一类图着色问题解法（此处暂列，等学习了更好的方法，更新还会）：

可以通过回溯法进行判定：对所有顶点枚举所有可能颜色。

如下C语言程序可供参考

#include<stdio.h>
#include<stdlib.h>

//用邻接表表示图

typedef struct child_node    //连接表中，一个图节点的邻接节点的数据结构  
{
        int node_num;
        struct child_node* next_child;
}child_node;
typedef struct graph_node   //图节点的数据结构
{
        int node_num;
        struct graph_node* next_node;
        child_node* first_child;
}graph_node;

 

int isok(graph_node* first_node,int step,int* colors)
{
        int i;
        graph_node* node_step=first_node;
        while(node_step->node_num!=step)  //找到编号为step的图节点
        {
                node_step=node_step->next_node;
        }

        child_node* child_of_step=node_step->first_child; 

        while(child_of_step!=NULL)  //遍历编号为step的图节点的邻接点
        {

                //编号小于step的colors值才有效，所以在if语句中加入了对节点编号的判断
                if((child_of_step->node_num<step)&&(colors[step]==colors[child_of_step->node_num]))
                        return 0;
                child_of_step=child_of_step->next_child;
        }
        return 1;
}

int DFS(graph_node* first_node,int node_nums,int step,int* colors,int color_num)
{
        if(step>=node_nums)   //表示回溯法进行到了最后一个图节点
                return 1;
        int i=0;
        for(i=0;i<color_num;i++)  //对所有颜色进行枚举
        {
                colors[step]=i; 
                if(isok(first_node,step,colors))
                {
                        if(DFS(first_node,node_nums,step+1,colors,color_num))  //回溯法往下递归
                                return 1;
                }
                colors[step]=0;  //回溯失败，返回时做的处理
        }
        return 0;
}

 

void init_graph(graph_node** p_first_node_of_the_graph,int node_nums,int edge_nums)
{
        int i;
        for(i=0;i<node_nums;i++)   //创建图节点
        {
                if(i==0)
                {
                        *p_first_node_of_the_graph=(graph_node*)malloc(sizeof(graph_node));
                        (*p_first_node_of_the_graph)->next_node=NULL;
                        (*p_first_node_of_the_graph)->first_child=NULL;
                        (*p_first_node_of_the_graph)->node_num=i;
                }
                else
                {
                        graph_node* temp=*p_first_node_of_the_graph;
                        while(temp->next_node!=NULL)
                                temp=temp->next_node;
                        temp->next_node=(graph_node*)malloc(sizeof(graph_node));
                        temp->next_node->next_node=NULL;
                        temp->next_node->first_child=NULL;
                        temp->next_node->node_num=i;
                }
        }

        for(i=0;i<edge_nums;i++)  //读入每条边，并把边的信息存入邻接表中
        {
                graph_node* temp=*p_first_node_of_the_graph;
                int j=0,b=0,e=0;
                printf("please input the %dth edge of the graph\n",i);
                scanf("%d %d",&b,&e);
                while(temp->node_num!=b)
                        temp=temp->next_node;
                child_node* ch_temp=temp->first_child;
                if(ch_temp==NULL)
                {
                        temp->first_child=(child_node*)malloc(sizeof(child_node));
                        temp->first_child->node_num=e;
                        temp->first_child->next_child=NULL;
                }
                else
                {
                        while(ch_temp->next_child!=NULL)
                                ch_temp=ch_temp->next_child;
                        ch_temp->next_child=(child_node*)malloc(sizeof(child_node));
                        ch_temp->next_child->next_child=NULL;
                        ch_temp->next_child->node_num=e;
                }

                temp=*p_first_node_of_the_graph;
                while(temp->node_num!=e)
                        temp=temp->next_node;
                ch_temp=temp->first_child;
                if(ch_temp==NULL)
                {
                        temp->first_child=(child_node*)malloc(sizeof(child_node));
                        temp->first_child->node_num=b;
                        temp->first_child->next_child=NULL;
                }
                else
                {
                        while(ch_temp->next_child!=NULL)
                                ch_temp=ch_temp->next_child;
                        ch_temp->next_child=(child_node*)malloc(sizeof(child_node));
                        ch_temp->next_child->next_child=NULL;
                        ch_temp->next_child->node_num=b;
                }
        }
}

 

//释放图所占的内存空间，first_node_of_the_graph是图的第一个节点的地址

void delete_graph(graph_node* first_node_of_the_graph)
{
        graph_node* temp=first_node_of_the_graph;
        graph_node* temp1;
        while(temp!=NULL)
        {
                child_node* ch_temp=temp->first_child;
                child_node* ch_temp1;
                while(ch_temp!=NULL)
                {
                        ch_temp1=ch_temp;
                        ch_temp=ch_temp->next_child;
                        free(ch_temp1);
                }
                temp1=temp;
                temp=temp->next_node;
                free(temp1);
        }
}

int main()
{
        int node_nums;   //图的节点数
        int edge_nums;  //图的边数
        int colors[4]={0,0,0,0};

 

        graph_node* first_node_of_the_graph=NULL;

        printf("please input the node_nums of the graph:\n");
        scanf("%d",&node_nums);
        printf("please input the edge_nums of the graph:\n");
        scanf("%d",&edge_nums);

 

        init_graph(&first_node_of_the_graph,node_nums,edge_nums);
        int is_the_color_num_ok= DFS(first_node_of_the_graph,node_nums,0,colors,3);

        if(is_the_color_num_ok==0)
                printf("The color num is too few.\n");
        else
                printf("The color num is ok.\n");

     

        delete_graph(first_node_of_the_graph);
        return 0;
}

2、第二类图着色问题有三种解法

     第一种解法：对编号为0的图节点着一种颜色，然后对剩下的n-1个顶点枚举其所有的颜色可能，在一一验证是否可以满足相邻节点不同色的条件。

     第二种解法：我们可以尝试对图进行K中着色，首先K设为1，看看有没有合适的方案，再逐渐把K提高。当假设待求解的图值最少着色远小于图的顶点数时，这种方法的复杂度较低。

     第三种解法：在第一类问题的回溯解法中，在DFS函数中记录一下用到的最大颜色值。把color_num设的足够大，当DFS函数成功返回时，这个最大颜色值加1就是所需要颜色的最少种类数。

 

     下面是对应第二种解法的C语言实现（这里只有main函数和上面的程序不相同，所以这里只给出main函数）：

 int main()
{
        int node_nums;
        int edge_nums;
        int colors[4]={0,0,0,0};

        graph_node* first_node_of_the_graph=NULL;

        printf("please input the node_nums of the graph:\n");
        scanf("%d",&node_nums);
        printf("please input the edge_nums of the graph:\n");
        scanf("%d",&edge_nums);

        init_graph(&first_node_of_the_graph,node_nums,edge_nums);

        int color_numbers=1;
        int is_the_color_num_ok= DFS(first_node_of_the_graph,node_nums,0,colors,color_numbers);
        while(is_the_color_num_ok==0) //color_numbers从1开始，逐渐增长，直到满足条件为止
        {
                color_numbers++;
            is_the_color_num_ok= DFS(first_node_of_the_graph,node_nums,0,colors,color_numbers);
        }
        printf("the color number needed to color the graph is %d\n",color_numbers);

        delete_graph(first_node_of_the_graph);
        return 0;
}

 

   第三中解法的C语言实现如下（很多都与上面重复了）：

#include<stdio.h>
#include<stdlib.h>

typedef struct child_node
{
        int node_num;
        struct child_node* next_child;
}child_node;
typedef struct graph_node
{
        int node_num;
        struct graph_node* next_node;
        child_node* first_child;
}graph_node;

int isok(graph_node* first_node,int step,int* colors)
{
        int i;
        graph_node* node_step=first_node;
        while(node_step->node_num!=step)
        {
                node_step=node_step->next_node;
        }

        child_node* child_of_step=node_step->first_child;

        while(child_of_step!=NULL)
        {
                if((child_of_step->node_num<step)&&(colors[step]==colors[child_of_step->node_num]))
                        return 0;
                child_of_step=child_of_step->next_child;
        }
        return 1;
}

int DFS(graph_node* first_node,int node_nums,int step,int* colors,int color_num,int* p_max_color)
{
        if(step>=node_nums)
                return 1;
        int i=0;
        for(i=0;i<color_num;i++)
        {
                colors[step]=i;
                if(i>(*p_max_color))
                        (*p_max_color)=i;
                if(isok(first_node,step,colors))
                {
                        if(DFS(first_node,node_nums,step+1,colors,color_num,p_max_color))
                                return 1;
                }
                colors[step]=0;
        }
        return 0;
}

void init_graph(graph_node** p_first_node_of_the_graph,int node_nums,int edge_nums)
{
        int i;
        for(i=0;i<node_nums;i++)
        {
                if(i==0)
                {
                        *p_first_node_of_the_graph=(graph_node*)malloc(sizeof(graph_node));
                        (*p_first_node_of_the_graph)->next_node=NULL;
                        (*p_first_node_of_the_graph)->first_child=NULL;
                        (*p_first_node_of_the_graph)->node_num=i;
                }
                else
                {
                        graph_node* temp=*p_first_node_of_the_graph;
                        while(temp->next_node!=NULL)
                                temp=temp->next_node;
                        temp->next_node=(graph_node*)malloc(sizeof(graph_node));
                        temp->next_node->next_node=NULL;
                        temp->next_node->first_child=NULL;
                        temp->next_node->node_num=i;
                }
        }

        for(i=0;i<edge_nums;i++)
        {
                graph_node* temp=*p_first_node_of_the_graph;
                int j=0,b=0,e=0;
                printf("please input the %dth edge of the graph\n",i);
                scanf("%d %d",&b,&e);
                while(temp->node_num!=b)
                        temp=temp->next_node;
                child_node* ch_temp=temp->first_child;
                if(ch_temp==NULL)
                {
                        temp->first_child=(child_node*)malloc(sizeof(child_node));
                        temp->first_child->node_num=e;
                        temp->first_child->next_child=NULL;
                }
                else
                {
                        while(ch_temp->next_child!=NULL)
                                ch_temp=ch_temp->next_child;
                        ch_temp->next_child=(child_node*)malloc(sizeof(child_node));
                        ch_temp->next_child->next_child=NULL;
                        ch_temp->next_child->node_num=e;
                }

                temp=*p_first_node_of_the_graph;
                while(temp->node_num!=e)
                        temp=temp->next_node;
                ch_temp=temp->first_child;
                if(ch_temp==NULL)
                {
                        temp->first_child=(child_node*)malloc(sizeof(child_node));
                        temp->first_child->node_num=b;
                        temp->first_child->next_child=NULL;
                }
                else
                {
                        while(ch_temp->next_child!=NULL)
                                ch_temp=ch_temp->next_child;
                        ch_temp->next_child=(child_node*)malloc(sizeof(child_node));
                        ch_temp->next_child->next_child=NULL;
                        ch_temp->next_child->node_num=b;
                }
        }
}

void delete_graph(graph_node* first_node_of_the_graph)
{
        graph_node* temp=first_node_of_the_graph;
        graph_node* temp1;
        while(temp!=NULL)
        {
                child_node* ch_temp=temp->first_child;
                child_node* ch_temp1;
                while(ch_temp!=NULL)
                {
                        ch_temp1=ch_temp;
                        ch_temp=ch_temp->next_child;
                        free(ch_temp1);
                }
                temp1=temp;
                temp=temp->next_node;
                free(temp1);
        }
}

int main()
{
        int node_nums;
        int edge_nums;
        int colors[4]={0,0,0,0};

        graph_node* first_node_of_the_graph=NULL;

        printf("please input the node_nums of the graph:\n");
        scanf("%d",&node_nums);
        printf("please input the edge_nums of the graph:\n");
        scanf("%d",&edge_nums);

        init_graph(&first_node_of_the_graph,node_nums,edge_nums);

        int color_numbers=15;
        int max_color;
        int is_the_color_num_ok= DFS(first_node_of_the_graph,node_nums,0,colors,color_numbers,&max_color);
        max_color++;

        printf("the color number needed to color the graph is %d\n",max_color);

        delete_graph(first_node_of_the_graph);
        return 0;
}