编写一个函数，判断一个图是否是有向无环图（DAG）。

小九九

判断一个图是否是有向无环图（DAG）可以使用拓扑排序算法。下面是一个判断函数的示例：

1. from collections import defaultdict
   
2. 
   
3. def is_dag(graph):
   
4.     # 统计每个顶点的入度
   
5.     indegree = defaultdict(int)
   
6.     for node in graph:
   
7.         for neighbor in graph[node]:
   
8.             indegree[neighbor] += 1
   
9.    
   
10.     # 初始化一个队列，将入度为 0 的顶点加入队列
    
11.     queue = []
    
12.     for node in graph:
    
13.         if indegree[node] == 0:
    
14.             queue.append(node)
    
15.    
    
16.     # 通过拓扑排序判断是否是 DAG
    
17.     while queue:
    
18.         current = queue.pop(0)
    
19.         for neighbor in graph[current]:
    
20.             indegree[neighbor] -= 1
    
21.             if indegree[neighbor] == 0:
    
22.                 queue.append(neighbor)
    
23.    
    
24.     # 如果存在入度不为 0 的顶点，说明图中存在环路
    
25.     for node in graph:
    
26.         if indegree[node] > 0:
    
27.             return False
    
28.    
    
29.     return True
    

复制代码

这个函数使用拓扑排序的思想来判断图是否是 DAG。首先，统计每个顶点的入度，并将入度为 0 的顶点加入队列。然后，从队列中依次取出顶点，并将与之相连的顶点的入度减 1。如果某个顶点的入度减为 0，就将其加入队列。重复这个过程直到队列为空。如果所有顶点的入度都变为 0，说明图中不存在环路，即为 DAG。

例如，给定以下图的表示：

1. graph = {
   
2.     'A': ['B', 'C'],
   
3.     'B': ['D'],
   
4.     'C': [],
   
5.     'D': ['E'],
   
6.     'E': []
   
7. }
   

复制代码

调用 is_dag(graph) 将返回 True，因为这个图是有向无环图（DAG）。

值得注意的是，这个函数假设输入的图是以邻接表的形式表示的。其中，字典的键表示顶点，对应的值是一个列表，表示与该顶点相连的其他顶点。如果输入的图使用其他形式表示，需要进行适当的转换。