推移閉包を計算する際の再帰アルゴリズムと反復アルゴリズムのさまざまなアプローチを比較する

def transitive_closure_recursive(adjacency_matrix): """ 递归算法求解传递闭包 Args: adjacency_matrix: 邻接矩阵 Returns: transitive_closure: 传递闭包矩阵 """ n = len(adjacency_matrix) # 图的节点数 transitive_closure = [[0] * n for _ in range(n)] # 初始化传递闭包矩阵 # 递归函数 def dfs(i, j): transitive_closure[i][j] = 1 # 将节点i传递到节点j标记为1 for k in range(n): if adjacency_matrix[j][k] and not transitive_closure[i][k]: dfs(i, k) # 递归调用 # 对每对节点进行遍历 for i in range(n): for j in range(n): if adjacency_matrix[i][j] and not transitive_closure[i][j]: dfs(i, j) # 调用递归函数进行遍历 return transitive_closure

def transitive_closure_iterative(adjacency_matrix): """ 迭代算法求解传递闭包 Args: adjacency_matrix: 邻接矩阵 Returns: transitive_closure: 传递闭包矩阵 """ n = len(adjacency_matrix) # 图的节点数 transitive_closure = [[0] * n for _ in range(n)] # 初始化传递闭包矩阵 for i in range(n): for j in range(n): if adjacency_matrix[i][j]: transitive_closure[i][j] = 1 # 将直接可达的节点标记为1 # 迭代更新传递闭包矩阵 for k in range(n): for i in range(n): for j in range(n): transitive_closure[i][j] = transitive_closure[i][j] or (transitive_closure[i][k] and transitive_closure[k][j]) return transitive_closure