A
B
C
D
E
a
1
1
1
0
0
b
1
0
1
0
0
c
0
0
0
1
0
d
0
1
0
0
1
表 1
A
B
C
D
E
A
2
1
2
0
0
B
1
2
1
0
1
C
2
1
2
0
0
D
0
0
0
1
0
E
0
1
0
0
1
表 2
Step1:随机选取表 1 中 1 的位置变成 0
在这个过程中存在特殊情况:当 A 对应的那一列所有数字为 0 的话,B,C,D,E 所有列都为 0
若 D 的哪一列都为 0,则 E 的列都变成 0
Step2:将改变后的表 1’转换成表 2 的形式
表 1 与表 2 的关系:对角线的位置为每列有 1 的个数 eg:表 2(1,1)的位置为 2,表示表 1
中第一列一共有 2 个 1.
除对角线的位置,表 2(i,j)位置的数据表示表 1 中第 i 列和第 j 列在同一行同时拥有
1 的次数 eg:(1,2)位置的 1 表示第 1 列和第 2 列一共有 1 次在同一行有 1。
Step3:计算出此时任意两点之间的最短路径 dij
Step4: 代入公式:X=
1
n(n−1)
∑
i
≠
j
1
d
ij
最开始的值即为 Y
算出每种情况下 (Y-X)/Y 记为 Z
Step5: 输出 Z,以及该情况被破坏的各节点的频次
(Z1 是 A 该行的两个 1,B 的一个 1)
则对 Z1 进行划分,2/3 记为 A1.1/3 记为 B1
Step6: 对 A.B.C.D 下的所有情况进行累计求和,输出最终的 A.B.C.D