好久没写东西了。最近几天翻了一下脚python算法教程的书，感觉有些东西还是挺有意思的，挑一个还算常用的算法拿出来说说。
场景是这样的，比如有a1~a10共10个人进行排队，比如a6必须排在a2和a5的后面，a4必须排在a7、a9、a6的后面，a3要在a8的后面，a5要在a3、a7和a10的后面，现在要求将10人排成一队，该怎么排呢？
换成脚本也是一样的道理，比如a6必须排在a2和a5的后面执行可以看做是脚本a6依赖脚本a2和脚本a5，可以想象10个脚本还好，倘若是1000个脚本，且依赖关系更复杂，直觉上就很难排的清了，那怎么样能抽丝剥茧解决这个问题呢？
这里用到的是一步步减少人数的方法，具体怎么个减少法呢，我们现在把问题简化，a,b,c 3人排队，要求b在a后面，c在b后面，这样我们马上能看出顺序应该是abc，如果分步应该如何实现呢，首先我们看到a没有约束要在谁的后面执行，所以a可以提前安排，安排好a之后，只剩b和c，同时因为a被安排，b必须在a后面的条件也不起作用了，于是b就没有约束条件限制了，此时就可以把b也安排在a后面，然后c的限制条件也消失了，这样问题规模就从3缩小到1了。
回到最开始提到的问题，准备用程序来解决这个问题，那首先要解决的是怎么表示这个依赖的结构了，可以用python自带的字典和集合结构，如下代码：
# 其实这个表示形式就是图的邻接集合表示
g_map = {
'a1': {},
'a2': {'a6'},
'a3': {'a5'},
'a4': {'a5'},
'a5': {},
'a6': {'a4'},
'a7': {'a4', 'a5'},
'a8': {'a3'},
'a9': {'a4'},
'a10': {'a5'}
}
接下来呢，要用一个字典存储每个人的前面确定要排的人的个数
# 初始化每个人的计数都是0，遍历确定每个人前面排多少人
dic_cnt = {u: 0 for u in g_map}
for u in g_map:
for v in g_map[u]:
dic_cnt[v] += 1
接下来就是不断迭代，将每次迭代中前面确定要排的个数为0个人的人拿出来，并将确定排在这些人后面的人的计数器减一，循环往复，直到遍历完整个列表：
# 初始化当前前面确定要排的个数为0个人的人的列表
undepen_list = [k for k, v in dic_cnt.items() if v == 0]
# 进入迭代
while undepen_list:
for u in undepen_list:
# 当前无依赖的人从字典中清除，确保下一轮迭代不会重复计算这部分人
del dic_cnt[u]
# 将依赖当前列表的人的计数器减一
for v in g_map[u]:
dic_cnt[v] -= 1
# 打印每步迭代的执行结果
print(undepen_list)
# 更新新一轮无依赖的人的列表
undepen_list = [k for k, v in dic_cnt.items() if v == 0]
以下是执行结果，排列顺序是从第一行到最后一行，需要注意的是，这只是所有结果的其中之一，并不是所有可能结果都会展示出来，而且由于字典和集合都是无序的，每次执行得到的结果可能也不相同，但一定是满足前提条件的：
image.png
还有一点需要注意，就是此算法只能应用于有向无环图（DAG）,比如a5在a4后，a6在a5后，而a4又在a6后，这种情况是排不出队的，当然此算法也就不适用，但是此算法还是能检测出是否有环的，当上一轮dic_cnt的key个数和当前轮一致，就说明依赖关系中有环路存在。
说了半天，其实本篇所讲的就是基于广度优先的拓扑排序，类似的还有基于深度优先的拓扑排序，如果有机会，后续再介绍。
网友评论