一般性骨架矩阵计算(保留环内信息方法)的详细过程


此处输入要素的个数:

返回首页




显示的是一个随机 12 * 12 的方阵



   01234567891011
0       1                           
1                            1      
2                         1       1
3                                  1
4                                    
5    1                   1         
6                         1    1   
7          1                1      
8    1       1    1               
9                1 1 1            
10    1                              
11                1                  

利用深搜算法获得所有环路,并得到有序图



0要素
1要素
2要素
3要素
4要素
5要素
6要素
7要素
8要素
9要素
10要素
11要素
第0层
第1层
第2层
第3层

根据层级由上往下进行计算,最上的层级为0



当前为:0 层,包含有 1 个要素
        当前向上的箭头,或者可达集合小于2,不用缩减
        本层的最后缩减集合为:  ( 4 到达的结点为:空)
当前为:1 层,包含有 9 个要素
        当前向上的箭头,或者可达集合小于2,不用缩减
        本层的最后缩减集合为:       本层剩余的出边到达结点为:4   1 环内的的:9   ( 1 到达的结点为:9)       本层剩余的出边到达结点为:4   3 环内的的:11   ( 3 到达的结点为:11)       本层剩余的出边到达结点为:4   5 环内的的:1+8   ( 5 到达的结点为:1+8)       本层剩余的出边到达结点为:4   6 环内的的:8+10   ( 6 到达的结点为:8+10)       本层剩余的出边到达结点为:4   7 环内的的:3+9   ( 7 到达的结点为:3+9)       本层剩余的出边到达结点为:4   8 环内的的:1+6   ( 8 到达的结点为:1+6+4)   9 环内的的:5+6+7   ( 9 到达的结点为:5+6+7)   10 环内的的:1   ( 10 到达的结点为:1)   11 环内的的:5   ( 11 到达的结点为:5)
当前为:2 层,包含有 1 个要素
       判断向上的箭头是否指向同一个环路
              8号要素8 在 1层 我访问到了
              11号要素11 在 1 层这个层级访问过了,删除11
        本层的最后缩减集合为:  ( 2 到达的结点为:8)
当前为:3 层,包含有 1 个要素
        当前向上的箭头,或者可达集合小于2,不用缩减
        本层的最后缩减集合为:  ( 0 到达的结点为:2)

得到阵骨架矩阵



   01234567891011
0       1                           
1                            1      
2                         1         
3                                  1
4                                    
5    1                   1         
6                         1    1   
7          1                1      
8    1       1    1               
9                1 1 1