图着色算法 - 分配颜色

Question

我这里有一个图表着色算法的函数，它为许多课程分配颜色。但是它是随机选择的，我想改进算法并比根据可用颜色随机选择一种更有效地分配颜色。

在这个函数中，N是时间安排的个数。

void create_schedule(int **graph, list *courses, int numcourses){
    int i, j, k, col=0;
    for(i=0; i<numcourses; i++){
        for(j=0; j<N; j++){
            for(k=0; k<i; k++){
                if(graph[i][k] > 0 && courses[k].color == j) break;
            }
            //color j was not yet chosen by adjacent nodes
            if(k >= i){
                courses[i].color = j;
                break;
            }
        }
        //if there is no color available, choose randomly
        if(j >= N){
            col = rand()%N;
            courses[i].color = col;
        }
    }
}

最好有解释。

Answer 1

首先，让我们定义问题 canColor(graph, k) - 当且仅当您可以 graph coloring 使用 k 种颜色绘制图形时，它才会回答正确。

canColor的伪代码：

canColor(graph, k):
   if graph is completely colored:
        return checkIfColoringValid(graph)
   v = first uncolored vertex
   for each i from 1 to k (inclusive)
       color v with color i
       //can add optimization here to trim upfront unsuccesful results
       res = canColor(graph,k)
       if res == true:
           return true
   //no answer found
   uncolor v (mark it as color[v] = 0)
   return false

以上是图着色decision problem

现在，我们需要用它来找到最佳着色。
请注意，如果 canColor(graph,k) == true，则 canColor(graph,k+1) == true

这意味着，你有一个隐喻的答案数组，0,0,..0,1,1,...,1，一旦有一些 k 的解决方案，k 之后的所有值也将有一个解决方案.这个隐喻数组是排序的，所以你可以在它上面应用 binary search （而不是访问数组，你每次计算 canColor(graph,k) 的答案），以获得 k 的最佳值 -您可以使用的颜色数量。

图着色算法 - 分配颜色

Graph Coloring Algorithm - Assign color

c

algorithm

scheduler

graph-coloring