拓扑排序

AOV - 网

以顶点表示活动，有向边表示活动之间的先后关系的图称为 AOV 网 (Activity On Vertex Network，顶点表示活动的网)。AOV 网是一种有向无环图 (Directed Acyclic Graph, DAG)。

拓扑排序就是将 AOV 网中的所有顶点排列成一个线性序列，并且序列满足以下条件：在 AOV 网中，如果从顶点 A 到 B 存在一条路径，则在该线性序列中，顶点 A 一定出现在顶点 B 之前。因此拓扑排序的过程就是将 AOV 网中的各个活动组成一个可行的实施方案。此外拓扑排序也可以判断图中是否有环。拓扑排序并不唯一，有向无环图一定存在拓扑排序。

拓扑排序具体的算法步骤如下：

选择一个入度为 0 的顶点并输出。
从 AOV 网中删除此顶点及以此顶点为起点的所有关联边。
重复上述两步，直到不存在入度为 0 的顶点为止。
AOV 网中还有剩余的顶点，则说明 AOV 网中存在回路，不是一个标准的 AOV 网。

代码实现

需要维护一个入度为 0 的顶点的集合，每次从该集合中取出 (没有特殊的取出规则，随机取出也行，使用队列 / 栈也行，下同) 一个顶点，将该顶点放入保存结果中。
紧接着循环遍历由该顶点引出的所有边，从图中移除这条边，同时获取该边的另外一个顶点，如果该顶点的入度在减去本条边之后为 0，那么也将这个顶点放到入度为 0 的集合中。然后继续从集合中取出一个顶点。
当集合为空之后，检查图中是否还存在任何边，如果存在的话，说明图中至少存在一条环路。不存在的话则返回结果 List，此 List 中的顺序就是对图进行拓扑排序的结果。

def topoSort(graph):     
    in_degrees = dict((u,0) for u in graph)   #初始化所有顶点入度为0     
    num = len(in_degrees)     
    for u in graph:         
        for v in graph[u]:             
            in_degrees[v] += 1    #计算每个顶点的入度     
    Q = [u for u in in_degrees if in_degrees[u] == 0]   # 筛选入度为0的顶点     
    Seq = []     
    while Q:         
        u = Q.pop()       #默认从最后一个删除         
        Seq.append(u)         
        for v in graph[u]:             
            in_degrees[v] -= 1    #移除其所有出边
            if in_degrees[v] == 0:        
                Q.append(v)          #再次筛选入度为0的顶点
    if len(Seq) == num:       #输出的顶点数是否与图中的顶点数相等
        return Seq     
    else:         
        return None

G = {
    'a':'bf',
    'b':'cdf',
    'c':'d',
    'd':'ef',
    'e':'f',
    'f':''
}
print(topoSort(G))

TensorFlow 计算图

TensorFlow 是一个使用数据流图 (Dataflow Graph) 表达数值计算的开源软件库。它使用节点表示抽象的数学计算，并使用 OP 表达计算的逻辑；而边表示节点间传递的数据流，并使用 Tensor 表达数据的表示。数据流图是一种有向无环图 (DAG)，当图中的 OP 按照特定的 拓扑排序 依次被执行时，Tensor 在图中流动形成数据流，TensorFlow 因此而得名。

在分布式运行时，数据流图的被分裂为多个子图，并被有效地部署到集群中的多个机器上并发执行。在一个机器内，注册的子图被二次分裂为更小的子图，它们被部署在本地设备集上并发执行。TensorFlow 支持多种异构设备的分布式计算，包括 CPU, GPU, ASIC。 TensorFlow 跨平台的卓越表现，使得它能够灵活地部署在各种计算平台上，包括台式机、服务器、移动终端。

TensorFlow 最初由 Google Brain 的研究员和工程师们开发出来，用于开展机器学习和深度神经网络的研究，包括语言识别、计算机视觉、自然语言理解、机器人、信息检索。但是，TensorFlow 系统架构的通用性和灵活性，使其广泛地用于其他科学领域的数值计算。