JAVA高级面试进阶训练营视频教程

admin

　　一、前言

　　关于本文中用到的这种图着色解决方法，不知道有没前人提出过。如果说没人提出过，那么就算是一个新的解决方法吧，具体性能对比没深入研究，但是求出的解基本是和Graph Coloring Instances网站里面的最优解一样的。

　　我们都知道，很多问题都可以转化成图着色问题来进行解决，所以本文的例子直接是无向图。

　　二、解决思路　　

　　不太成熟的想法：

　　要使得相邻点的颜色不同，着色方案有很多种，那么究竟哪种着色方案使用的颜色最少呢？

　　首先最开始看到这个问题时，我最开始的思路是每次用尽量少的颜色给尽量多的点上色。

　　

->->->->->

　　以上是个简单的图，我选用的步骤为：

　　1、找出度最大的顶点2、3、5（度均为4）。

　　2、对2着色C1，然后遍历相邻点

　　3、给1着色C2

　　4、给3着色C2，和1冲突，着色C3

　　5、给5着色C2，不冲突

　　6、给4着色C2，与5冲突，着色C3

　　7、给4着色C1，不冲突

　　从一次性上完一种颜色入手：

　　本来是想实现上一个想法的，但是在梳理的过程中，有一个新的想法，即是通过与以前运筹学课程上学过的方法结合，较为高效且高质量地解决问题。

　　步骤如下：

　　步骤一、给未上色点集中度最大的顶点上色Ci，生成可同色点集，为与该顶点不相邻且未上色的点的集合

　　步骤二、遍历可同色点集，给点集中的点上色Ci，每上完一个点就生成一次可同色点集，为与上Ci点不相邻且未上色的点的集合，直到可同色点集为空

　　步骤三、更新未上色点集，i=i+1，回到步骤一

　　例：以下是myciel3.col数据的图，求最少能上几种颜色。

　　

　　邻接矩阵为

　　

 　　每个顶点的度为4、4、4、4、4、3、3、3、3、3、5，度最大的顶点为第11个顶点。

　　1、给V11上色C1，可同色集为{V1，V2，V3，V4，V5}

　　2、给V1上色C1，可同色集为{V3，V5}

 　　3、给V3上色C1，可同色集为{}

　　4、给V2上色C2，可同色集为{V4，V7，V9，V10}　　

 　　5、给V4上色C2，可同色集为{V7，V9}

　　6、给V7上色C2，可同色集为{V9}

　　7、给V9上色C2，可同色集为{}

 　　8、给V5上色C3，可同色集为{V6，V8，V10}

　　9、给V6上色C3，可同色集为{V10}

　　10、给V10上色C3，可同色集为{}

　　11、给V8上色C4，可同色集为{}

　　上色后的图：

　　

　　颜色使用了4种，和已知最优解一样。

 

　　三、python代码实现

　　

 1 def getAdjMatrix(path):
 2     edge = []
 3     pointNum = 0
 4     with open(path, 'r') as fp:
 5         for line in fp.readlines():
 6             if line.startswith('p'):
 7                 pointNum = int(line.split()[2])
 8                 for i in range(pointNum):
 9                     edge.append([0 for i in range(pointNum)])
10             if line.startswith('e') and pointNum > 0:
11                 edge[int(line.split()[1]) - 1][int(line.split()[2]) - 1] = 1
12                 edge[int(line.split()[2]) - 1][int(line.split()[1]) - 1] = 1
13     return edge, pointNum
14 
15 
16 def main():
17     edge, pointNum = getAdjMatrix(r'F:\timFilm\test.txt')
18     print('')
19     for i in edge:
20         print('    ', end='')
21         for j in i:
22             print(j, end='\t\t')
23         print('\n')
24     colorNum = 0
25     disabled = []
26 
27     # 初始化color列表，用以记录每个顶点的着色情况
28     color = []
29     for i in range(pointNum):
30         color.append(0)
31     edgeNum = [sum(e) for e in edge]
32     for k in range(pointNum):
33         # 获取顶点最大度的索引值
34         maxEdgePoint = [i for i in range(pointNum) if edgeNum == max(edgeNum) and edgeNum != 0]
35         # 遍历最大度
36         for p in maxEdgePoint:
37             if p not in disabled:
38                 # 选取还未着色且度最大的点p开始着色
39                 color[p] = colorNum + 1
40                 disabled.append(p)
41                 edgeNum[p] = 0
42                 # temp用于查找该颜色可用来着色的下一个顶点
43                 temp = edge[p]
44                 for i in range(pointNum):
45                     if i not in disabled:
46                         if temp == 0:
47                             # 为不冲突的顶点着色
48                             color = colorNum + 1
49                             disabled.append(i)
50                             edgeNum = 0
51                             # 增加当前颜色的禁忌点
52                             temp = [x + y for (x, y) in zip(edge, temp)]
53                 # 需要新颜色
54                 colorNum = colorNum + 1
55 
56         # 每个顶点都已经着色
57         if 0 not in color:
58             break
59     print(color)
60     print(colorNum)
61 
62 
63 main()