图着色问题：给定任意一个图，有N个节点，分别对应不同的权值。给图中的节点用k种颜色着色，（k<N）。

图着色问题：给定任意一个图，有N个节点，分别对应不同的权值。给图中的节点用k种颜色着色，（k<N）。

建立一个k大小的堆
遍历一遍图，每次都尝试把遍历到的值放入堆中，前提是，它要比堆（是按大小排序的）中最大的值小；
最后得出的是图中所有节点中权值最小的k个
再把颜色权值中为0的，分配给k个节点中权值稍大的几个
最后得出的就是权值相乘总和最小的涂色方案
追问可能我没有表达清楚，我的问题需要两个条件：
图的着色，要求一条边上的两个顶点不能着同一色。（你的算法好像这一点不满足）
能着色尽量着色，只有在不得已的情况下，才会去找那个不用着色的顶点。
追答不是有k种颜色么，而上面的算法只使用了k种颜色，所以你的附加条件1是满足的，至于条件2，你可以在得出最小值后，再补充着色追问你的算法好像只是找到k个节点，然后只对这k个节点着色。若接着补充着色的话，可能会对节点权值大的使用到权值为1的颜色，这样最后还是不一定得到最优解，也不一定在大多数情况下得到最优解。追答想了下，换个思路：
抛开给定的k种颜色，先计算整个图一共需要多少种颜色，而这其实是计算图中，每两个节点都相连的子图形中，节点数目最多有多少个，如：一个三角形的图，每两个都相连的节点有3个，则最多需要3种颜色，而一个正方形的图，每两个都相连的节点则有2个，最多需要两种颜色
以上面的概念为基础，依次遍历整个图，并寻找所有的节点两两相连的子图形：
对于第一个节点，记为P1，而其颜色记为C1
然后遍历和其直接相连的节点，记为P2，而其颜色记为C2，并将颜色需要个数提升为2
继续遍历和P1直接相连的节点，并判断其是否也和P2相连，如果相连，则记为P3,C3，此时颜色至少需要3种；如果不相连，则将其作为和P1的另一个组合加以归类，可以使用递归的方法，找到完整的两两相连的子图形就回溯
如果和P1相连的节点只有P2，那么它们就是一个完整的子图形，从P2开始继续执行b和c步；
在遍历的同时，完成颜色的分配，当一个子图形没有和任何其它已找到的图形重叠时（第一个图形或者是整个图就是一个两两相连的子图形），那么颜色依次为C1 C2...Cn；当图行有重叠时，即发现的新子图形中，某些节点已经分配了颜色，则以当前需要的颜色数量和已分配的颜色，来推出新节点的颜色；某些时候 ，节点颜色可以有多种可能，则记下所有可能性，在后面计算时，再做决定
 
以下图为例（注意，P1和P5不直接相连），可以得到，其包含四个子图形，每个子图形都包含3个节点，则整个图至少需要3种颜色

 
假定节点权值为：
P1 = 20, P2 = 22, P3 = 14, P4 = 16, P5 = 12
      
子图形：   {P1, P2, P3}  {P1, P2, P4}  {P2, P3, P5} {P2, P4, P5}
对应颜色：{C1, C2, C3} {C1, C2, C3} {C2, C3, C1} {C2, C3, C1}

如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！

点此我要举报以上问答信息