中山大学数据科学与计算机学院本科生实验报告
课程名称:编译器构造实验 任课教师:陈炬桦 教学助理(TA):
1. 实验题目
传递闭包的 Warshall 算法
1.1 Description
传递闭包 的 Warshall 算法为:
for j:=1 until N do
for i:=1 until N do
if M[i,j]=1 then for k:=1 until N do
M[i,k]:= M[i,k]∨M[j,k]
输入矩阵 M(R),计算并输出 M(R+)。
1.2 Input
输入 M 方阵的行列数;
输入矩阵 M(R);
1.3 Output
计算并输出 M(R+),每个符号占 3 格;
2. 算法描述(介绍程序模块功能;流程图)
算法为三重 for 循环。我们可以把状态写成三维(f[k][i][j]),f[k][i][j]表示的是只经过 1…k 这
些节点的情况下,i 到 j 是否可达。考虑从 k 转移到 k+1,若 ij 不需要经过 k+1,则 f[k+1][i][j]
评论0