图--拓扑排序

计算机科学家几乎可以将所有的问题转换为图问题。
计算松饼的例子举例说明拓扑排序。

松饼的制作步骤使用图来表示：
借助拓扑排序确定松饼制作的步骤。

上图是一个有向无环图，经常用于表示事件的优先级。常见的例子有：软件项目调度、由阿胡数据库查询、举矩阵相乘。

拓扑排序是基于深度优先搜索的DFS，算法大致如下：

1. 对图g调用深度优先搜索dfs(g). 计算每一个顶点结束的时间。
2. 根据结束时间，将定顶点按照递减的顺序存储在列表中。
3. 将列表作为拓扑排序返回。

以下是制作松饼的深度优先搜索图：

将结果排序得到拓扑排序：

代码:

from pythonds import Graph, Vertex


# 创建图
# 实现深度DFS
# 将结果排序


# 实现DFS
# 因为要记录每一个顶点的时间，所以用子类实现
class DFSGraph(Graph):
    def __init__(self):
        super().__init__()
        self.time = 0

    def dfs(self):
        for v in g:
            v.setColor('white')
        """确保每一个顶点都能访问到"""
        for v in self:
            if v.getColor() == 'white':
                self.dfsVisit(v)

    def dfsVisit(self, start_vertex):
        """深度搜索递归函数"""
        self.time += 1
        start_vertex.setColor('gray')
        start_vertex.setDiscovery(self.time)  # 第一次访问时间
        for nbr in start_vertex.getConnections():
            if nbr.getColor() == 'white':
                self.dfsVisit(nbr)
        # ###前面时递归进栈
        # ###后面是递归返回
        self.time += 1
        start_vertex.setFinish(self.time)  # 第二次访问时间
        start_vertex.setColor('black')


# 创建图
# 注意是有向图
g = DFSGraph()
g.addEdge('3/4杯牛奶', '一杯松粉')
g.addEdge('一个鸡蛋', '一杯松粉')
g.addEdge('一勺油', '一杯松粉')
g.addEdge('一杯松粉', '加热枫糖浆')
g.addEdge('一杯松粉', '倒入1/4杯')
g.addEdge('倒入1/4杯', '出现气泡时翻面')
g.addEdge('出现气泡时翻面', '开始享用')
g.addEdge('加热枫糖浆', '开始享用')
g.addEdge('加热平底锅', '倒入1/4杯')

# DFS
g.dfs()
# 拓扑排序

time_list = [(v.getId(), v.getDiscovery(), v.getFinish()) for v in g]
print(time_list)
sorted_list = sorted(time_list, key=lambda x: x[2], reverse=True)
print(sorted_list)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60