拓扑排序的邻接矩阵实现

拓扑排序是一种常用的有向无环图(DAG)的排序算法，它可以用来解决一些依赖关系的问题。邻接矩阵是一种常见的图表示方法，可以用二维数组来表示图中节点之间的连通关系。下面是一个使用邻接矩阵实现拓扑排序的示例代码：

from collections import deque

def topological_sort(adj_matrix):
    n = len(adj_matrix)
    indegree = [0] * n
    result = []
    
    # 计算每个节点的入度
    for i in range(n):
        for j in range(n):
            indegree[j] += adj_matrix[i][j]
    
    # 将入度为0的节点加入队列
    queue = deque()
    for i in range(n):
        if indegree[i] == 0:
            queue.append(i)
    
    # 拓扑排序
    while queue:
        node = queue.popleft()
        result.append(node)
        
        # 更新每个节点的入度
        for i in range(n):
            if adj_matrix[node][i] == 1:
                indegree[i] -= 1
                if indegree[i] == 0:
                    queue.append(i)
    
    # 检查是否有环
    if len(result) != n:
        print("图中存在环")
    
    return result

使用示例：

adj_matrix = [
    [0, 0, 1, 1, 0],
    [0, 0, 0, 1, 1],
    [0, 0, 0, 0, 1],
    [0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0]
]

result = topological_sort(adj_matrix)
print(result)

输出结果：

[0, 1, 2, 3, 4]

这段代码首先通过邻接矩阵计算每个节点的入度，然后将入度为0的节点加入队列中，并不断更新每个节点的入度，直到队列为空。最后检查排序结果的长度是否等于节点个数，如果不等说明图中存在环。