拓扑排序Topological Sort
❖从工作流程图得到工作次序排列的算法,称为“拓扑排序”
❖拓扑排序处理一个DAG,输出顶点的线性序列,使得两个顶点v,w,如果G中有(v,w)边,在线性序列中v就出现在w之前。
❖拓扑排序广泛应用在依赖事件的排期上,还可以用在项目管理、数据库查询优化和矩阵乘法的次序优化上
拓扑排序可以采用DFS很好地实现:
将工作流程建立为图,工作项是节点,依赖关系是有向边
工作流程图一定是个DAG图,否则有循环依赖对DAG图调用DFS算法,以得到每个顶点的“结束时间”
按照每个顶点的“结束时间”从大到小排序输出这个次序下的顶点列表
image.png
image.png
from basicGraph import Graph
class DFSGraph(Graph):
def __init__(self):
super().__init__()
self.time = 0
def dfs(self):
for v in self:
v.setColor('white')
v.setPred(None)
for v in self:
if v.getColor() == 'white':
self.dfsvisit(v)
def dfsvisit(self,startV):
startV.setColor('gray')
self.time += 1
startV.discoveryTime = self.time
for nbr in startV.getConnections():
if nbr.getColor() == 'white':
nbr.setPred(startV)
self.dfsvisit(nbr)
startV.setColor('black')
self.time+=1
startV.finishTime = self.time
if __name__ == '__main__':
g = DFSGraph()
g.addEdge('一个鸡蛋','一杯松仁粉')
g.addEdge('一勺油', '一杯松仁粉')
g.addEdge('牛奶', '一杯松仁粉')
g.addEdge('一杯松仁粉', '倒入混合物')
g.addEdge('加热平底锅', '倒入混合物')
g.addEdge('倒入混合物', '出现气泡翻面')
g.addEdge('一杯松仁粉', '加热糖浆')
g.addEdge('出现气泡翻面', '开始享用')
g.addEdge('加热糖浆', '开始享用')
#
for node in g:
print(node.getId(),node.discoveryTime,node.finishTime)
print('-'*70)
g.dfs()
lst = []
for node in g:
print(node.getId(),node.discoveryTime,node.finishTime)
lst.append(node)
# # 基于结束时间,将顶点按照递减顺序存储在列表中。
print('-'*70)
for node in lst:
print(node.getId(), node.finishTime)
lst.sort(key=lambda x:-x.finishTime)
for node in lst:
print(node.getId(),end=' ')