算法1.1--启发式算法实现图着色

启发式算法是指一种依赖于人的想法,采用试探性的逐步挖的求解方法.

 

以下程序使用贪心算法实现了图的着色,参数为输入文件与节点数,其中,输入文件以矩阵方式存储图,非0表示两节点可达/相临.

 

这种算法并不总能得到最优解,只保证得到近似最优解. 其实,顶点的编号方法决定了这种算法的结果.至少存在一种编号方法使这个贪心算法能得到最优解.

 

 

/*$ID:

 * Just for fun.:-)

 * gcc -Wall -o greedycolor greedycolor.c

 */

#include
#include
#include
#include

#define MAX_BUF 1024

int ** graph;
void usage(char * argv)
{
        printf("Usage %s [-h] [-p inputfile] [-n number_of_nodes]\n", argv);
        exit(0);
}

void my_exit(char * msg, int quit)
{
        printf("%s\n", msg);
        exit(quit);
}

void color_up(int nodes)
{
        int i, j, k = 1;
        int *color;
        color = (int*)malloc((sizeof(int))*(nodes+1));
        for(i = 1; i <= nodes; i ++)
                color[i] = 0;
        color[1] = 1;
        do
        {
                for(i = 2; i <= nodes; i ++)
                {
                        if(color[i] > 0) continue;
                        for(j = 1; j < i ; j ++)
                                if((color[j] == k) && (graph[i-1][j-1] != 0)) break;
                        if(j == i) color[i] = k;
                }
                j = 2;
                while((color[j] > 0) && (j <= nodes)) j++;
                k++;
        }while(j <= nodes);
        for(i = 1; i <=nodes; i ++)
                printf("node %d color: %d\n", i, color[i]);
}

int main(int argc, char * argv[])
{
        int opt, nodes_num = 0, i, j, k;
        char * pfile = NULL;
        FILE * fpfile;
        char * head;
        char * get;
        char buf[MAX_BUF];

        while((opt = getopt(argc, argv, "hp:n:")) != EOF)
        {
                switch(opt)
                {
                        case 'h':
                                usage(argv[0]);
                                break;
                        case 'p':
                                pfile = optarg;
                                break;
                        case 'n':
                                nodes_num = atoi(optarg);
                                if(nodes_num <= 0)
                                        my_exit("Please tell me how many nodes!", 100);
                                break;
                        default:
                                usage(argv[0]);
                                break;
                }
        }

        if((fpfile = fopen(pfile, "r")) == NULL)
        {
                my_exit("I can't open input file!", 99);
        }
        else
        {
                //allocate the array for the graph
                graph = (int **) malloc(sizeof(int *) * nodes_num);
                for(i = 0; i < nodes_num; i ++)
                        graph[i] = (int *)malloc(sizeof(int) * nodes_num);

                //initiate the array
                for(i = 0; i < nodes_num; i ++)
                {
                        if(fgets(buf, MAX_BUF, fpfile)!= NULL)
                        {
                                head = buf;
                                for(j = 0; j < (nodes_num - 1); j ++)
                                {
                                        get = strstr(head, " ");
                                        if(get != NULL)
                                                *get = '\0';
                                        else
                                        {
                                                for(i = 0; i < nodes_num; i ++)
                                                        free(graph[i]);
                                                free(graph);
                                                my_exit("Read input file error!", 98);
                                        }
                                        graph[i][j] = atoi(head);
                                        printf("%d ", graph[i][j]);
                                        head = get + 1;
                                }
                                graph[i][j] = atoi(head);
                                printf("%d ", graph[i][j]);
                                printf("\n");
                        }
                        else
                        {
                                for(i = 0; i < nodes_num; i ++)
                                        free(graph[i]);
                                free(graph);
                                my_exit("Invalid input file!", 98);
                        }
                }
                color_up(nodes_num);
        }

        //release the graph array
        for(i = 0; i < nodes_num; i ++)
                free(graph[i]);
        free(graph);
        return 1;
}