编写一个函数，判断一个图是否是有向无环图（DAG）。
判断一个图是否是有向无环图（DAG）可以使用拓扑排序算法。下面是一个判断函数的示例：from collections import defaultdict
def is_dag(graph):
# 统计每个顶点的入度
indegree = defaultdict(int)
for node in graph:
for neighbor in graph:
indegree += 1
# 初始化一个队列，将入度为 0 的顶点加入队列
queue = []
for node in graph:
if indegree == 0:
queue.append(node)
# 通过拓扑排序判断是否是 DAG
while queue:
current = queue.pop(0)
for neighbor in graph:
indegree -= 1
if indegree == 0:
queue.append(neighbor)
# 如果存在入度不为 0 的顶点，说明图中存在环路
for node in graph:
if indegree > 0:
return False
return True
这个函数使用拓扑排序的思想来判断图是否是 DAG。首先，统计每个顶点的入度，并将入度为 0 的顶点加入队列。然后，从队列中依次取出顶点，并将与之相连的顶点的入度减 1。如果某个顶点的入度减为 0，就将其加入队列。重复这个过程直到队列为空。如果所有顶点的入度都变为 0，说明图中不存在环路，即为 DAG。例如，给定以下图的表示：graph = {
'A': ['B', 'C'],
'B': ['D'],
'C': [],
'D': ['E'],
'E': []
}
调用 is_dag(graph) 将返回 True，因为这个图是有向无环图（DAG）。值得注意的是，这个函数假设输入的图是以邻接表的形式表示的。其中，字典的键表示顶点，对应的值是一个列表，表示与该顶点相连的其他顶点。如果输入的图使用其他形式表示，需要进行适当的转换。
页:
[1]