有向无环层次图实现

有向无环层次图（Directed Acyclic Graph, DAG）是一种图结构，其中顶点之间有方向性，且不存在环路。实现有向无环层次图可以使用拓扑排序算法。

拓扑排序算法可以按照顶点之间的依赖关系进行排序，即将图中的顶点按照一定的顺序排列，使得对于每一条有向边 (u, v)，顶点 u 在排序中出现在顶点 v 之前。

以下是一个使用拓扑排序算法实现有向无环层次图的代码示例：

from collections import defaultdict, deque

class DAG:
    def __init__(self):
        self.graph = defaultdict(list)
        self.indegree = defaultdict(int)
    
    def add_edge(self, u, v):
        self.graph[u].append(v)
        self.indegree[v] += 1
    
    def topological_sort(self):
        result = []
        queue = deque()
        
        # 将入度为0的顶点入队列
        for v in self.graph:
            if self.indegree[v] == 0:
                queue.append(v)
        
        while queue:
            u = queue.popleft()
            result.append(u)
            
            # 更新相邻顶点的入度
            for v in self.graph[u]:
                self.indegree[v] -= 1
                if self.indegree[v] == 0:
                    queue.append(v)
        
        # 如果存在环路，则图中存在至少一个顶点的入度始终不为0
        if len(result) != len(self.graph):
            return None
        
        return result

以上代码中，DAG 类使用 defaultdict 构建了一个邻接表来表示有向无环层次图，其中 graph 字典存储了每个顶点的相邻顶点，indegree 字典存储了每个顶点的入度。

add_edge 方法用于添加一条有向边，将边的起点和终点加入邻接表和入度字典中。

topological_sort 方法使用拓扑排序算法对图进行排序。它从入度为0的顶点开始，逐个将顶点出队列，并更新相邻顶点的入度。如果图中存在环路，则无法完成拓扑排序，返回 None；否则返回排序结果。

使用示例：

dag = DAG()
dag.add_edge('A', 'B')
dag.add_edge('A', 'C')
dag.add_edge('B', 'D')
dag.add_edge('C', 'D')
dag.add_edge('D', 'E')

result = dag.topological_sort()
if result:
    print("拓扑排序结果:", result)
else:
    print("图中存在环路")

输出：

拓扑排序结果: ['A', 'B', 'C', 'D', 'E']

以上代码实现了有向无环层次图的拓扑排序，可以根据实际需求进行扩展和修改。