数据结构学习python笔记（day1）

#绪论部分

##问题描述
一个五条路的交叉路口，其中两条路是单行线，其余是正常的双向行驶道路。

设计红绿灯组数满足两个条件：（安全问题）1.属同一组的各个方向行驶的车辆，均可以同时行驶，不出现相互交错的行驶路线，因此保证了安全和路线畅通。

（经济问题）2.所作分组尽可能大写，以提高路口效率。

##问题分析
首先罗列所有路口行驶方向，一共有13种可能：AB,AC,AD,BA,BC,BD,DA,DB,DC,EA,EB,EC,ED。

需要确定一些可以同时开绿灯的方向组。

也就是需要为所有可能方向做出一种安全分组，保证每组里行驶方向相互不冲突，可以同时放行。

进一步理解冲突的概念，例如，在允许BD方向的情况下，是否同时允许AD和ED，可能有不同的定义得到不同的解。

为了更清楚的弄清安全分组，将相互冲突的方向之间画成一条线，做一个冲突图。

矩形代表行驶方向，矩形之间有连线代表有冲突。

问题转换为：为冲突图中的顶点确定一种分组，保证属于同一组的所有顶点互不邻接。

这里期望一种分组较少的分组。

进一步转化为图最佳着色问题。

##伪代码
输入：图G #记录顶点连接关系
集合verts保存G中所有顶点 #建立初始状态
设置集合groups为空集 #记录得到的分组，元素是顶点集合
while存在未着色顶点： #每次迭代用贪心法找出一个新的分组
选一种新颜色
在未着色顶点中给尽量多的无互联边的点着色（构建一个分组）
记录新的着色的顶点组 #算法结束时返回groups里的分组方式
##代码
def coloring(G): #做图G的着色
color = 0
groups = set()
verts = vertices(G) #取得G的所有顶点，依赖于图的表示
while verts: #如果集合不空
new_group = set()
for v in list(verts):
if not_adjacent_with_set(v,newgroup,G): #not_adjacent_with_set检查v与group中各顶点在图G中
new_group.add(v) #是否有边连接
verts.remove(v)
groups.add((color,new_group))
color +=1
return groups

参考文献：[1]裘宗燕. 数据结构与算法:Python语言描述[M]. 机械工业出版社, 2016.