可达矩阵的四种求解方法：自乘，幂乘，Warshall转移闭包法、一次性Warshall法

~
计算方式
优缺点
自乘法

第一步：求出自乘矩阵。

第二步：相乘矩阵，乘以相乘矩阵，就是进行布尔积（Boolean Product）⊙运算。

第三步：自乘矩阵一直乘下去。

最后：得到的矩阵不再变化时，该矩阵就叫可达矩阵。

优点：数学表达式简单，好理解。通常计算都是用这种方法，大部分教科书也是用的这种方法。

缺点：运算慢。矩阵的布尔积运算次数多！
幂乘法

第一步：求出自乘矩阵。

第二步：相乘矩阵，乘以相乘矩阵，就是进行布尔积（Boolean Product）⊙运算。

第三步：得到的矩阵称之为幂矩阵，幂矩阵再相乘，一直这样平方下去。

最后：得到的矩阵不再变化时，该矩阵就叫可达矩阵。

优点：数学表达式简单，好理解。

缺点：运算慢。矩阵的布尔积运算次数多！

另外一个由于幂矩阵中的为1的值相对较多。其实际运算速度不一定就比自乘法快，虽然其，矩阵乘法运算次数相对于自乘法要少！
Warshall法

第一步：求出自乘矩阵。

第二步：相乘矩阵，得到转移矩阵。

第三步：转移矩阵的相对于自乘矩阵的转移矩阵，一直循环。

最后：得到的矩阵不再变化时，该矩阵就叫可达矩阵。

优点：运算速度中等。

缺点：稍微有点难理解！
改进Warshall法

第一步：求出自乘矩阵。

第二步：相乘矩阵，得到转移矩阵。

第三步：转移矩阵的转移矩阵，一直循环。

最后：得到的矩阵不再变化时，该矩阵就叫可达矩阵。

优点：运算速度中等。

缺点：稍微有点难理解！
一次性Warshall法

第一步：根据原始矩阵求出所有的强连通分量

第二步：根据强连通分量得到的是一个良好拓扑排序的矩阵

第三步：从上到下，进行一次Warshall运算就得到了可达矩阵。

优点：运算速度得到数量级的提高。

缺点：难理解！

在矩阵对角线下一个对角线上全部输入1，只要一次Wallshall就可以得出可达矩阵！



可达矩阵如下


$$R=\begin{array} {c|c|c|c|c|c|c|c}{M_{12 \times12}} &子 &丑 &寅 &卯 &辰 &巳 &午 &未 &申 &酉 &戌 &亥\\ \hline 子 &1 & & & & & & & & & & &1\\ \hline 丑 & &1 & & & & &1 & & & & &1\\ \hline 寅 & & &1 &1 & &1 &1 & &1 &1 & &1\\ \hline 卯 & & & &1 & & &1 & & & & &1\\ \hline 辰 & & & & &1 & &1 & &1 & & &1\\ \hline 巳 & & & &1 & &1 &1 & & & & &1\\ \hline 午 & & & & & & &1 & & & & &1\\ \hline 未 & & & &1 &1 &1 &1 &1 &1 &1 & &1\\ \hline 申 & & & & & & &1 & &1 & & &1\\ \hline 酉 & & & &1 & &1 &1 & &1 &1 & &1\\ \hline 戌 & & & &1 & &1 &1 & &1 &1 &1 &1\\ \hline 亥 & & & & & & & & & & & &1\\ \hline \end{array} $$

矩阵的表示形式


   子丑寅卯辰巳午未申酉戌亥
子                                  1
丑                   1               
寅                1          1      
卯                   1               
辰                         1         
巳          1                        
午                                  1
未             1             1      
申                   1               
酉                1       1         
戌                            1      
亥                                    

矩阵的表示形式


原始矩阵 可达矩阵
   子丑寅卯辰巳午未申酉戌亥
子                                  1
丑                   1               
寅                1          1      
卯                   1               
辰                         1         
巳          1                        
午                                  1
未             1             1      
申                   1               
酉                1       1         
戌                            1      
亥                                    
   子丑寅卯辰巳午未申酉戌亥
子 1                               1
丑    1             1             1
寅       1 1    1 1    1 1    1
卯          1       1             1
辰             1    1    1       1
巳          1    1 1             1
午                   1             1
未          1 1 1 1 1 1 1    1
申                   1    1       1
酉          1    1 1    1 1    1
戌          1    1 1    1 1 1 1
亥                                  1

可达矩阵的求解,其中其中快速（迭代）Warshall的转移闭包与逼近的可达矩阵的速度最快

矩阵相乘的次数 相乘矩阵自乘的方法 幂乘的方法 快速Warshall转移法
1
   子丑寅卯辰巳午未申酉戌亥
子 1                               1
丑    1             1               
寅       1       1          1      
卯          1       1               
辰             1          1         
巳          1    1                  
午                   1             1
未             1       1    1      
申                   1    1         
酉                1       1 1      
戌                            1 1   
亥                                  1
   子丑寅卯辰巳午未申酉戌亥
子 1                               1
丑    1             1               
寅       1       1          1      
卯          1       1               
辰             1          1         
巳          1    1                  
午                   1             1
未             1       1    1      
申                   1    1         
酉                1       1 1      
戌                            1 1   
亥                                  1
   子丑寅卯辰巳午未申酉戌亥
子 1                               1
丑    1             1               
寅       1       1          1      
卯          1       1               
辰             1          1         
巳          1    1                  
午                   1             1
未             1       1    1      
申                   1    1         
酉                1       1 1      
戌                            1 1   
亥                                  1
2
   子丑寅卯辰巳午未申酉戌亥
子 1                               1
丑    1             1             1
寅       1 1    1       1 1      
卯          1       1             1
辰             1    1    1         
巳          1    1 1               
午                   1             1
未             1 1    1 1 1      
申                   1    1       1
酉          1    1 1    1 1      
戌                1       1 1 1   
亥                                  1
   子丑寅卯辰巳午未申酉戌亥
子 1                               1
丑    1             1             1
寅       1 1    1       1 1      
卯          1       1             1
辰             1    1    1         
巳          1    1 1               
午                   1             1
未             1 1    1 1 1      
申                   1    1       1
酉          1    1 1    1 1      
戌                1       1 1 1   
亥                                  1
   子丑寅卯辰巳午未申酉戌亥
子 1                               1
丑    1             1             1
寅       1 1    1       1 1      
卯          1       1             1
辰             1    1    1         
巳          1    1 1             1
午                   1             1
未             1 1 1 1 1 1      
申                   1    1       1
酉          1    1 1    1 1    1
戌          1    1 1    1 1 1 1
亥                                  1
3
   子丑寅卯辰巳午未申酉戌亥
子 1                               1
丑    1             1             1
寅       1 1    1 1    1 1      
卯          1       1             1
辰             1    1    1       1
巳          1    1 1             1
午                   1             1
未          1 1 1 1 1 1 1      
申                   1    1       1
酉          1    1 1    1 1    1
戌          1    1 1    1 1 1   
亥                                  1
   子丑寅卯辰巳午未申酉戌亥
子 1                               1
丑    1             1             1
寅       1 1    1 1    1 1    1
卯          1       1             1
辰             1    1    1       1
巳          1    1 1             1
午                   1             1
未          1 1 1 1 1 1 1    1
申                   1    1       1
酉          1    1 1    1 1    1
戌          1    1 1    1 1 1 1
亥                                  1
   子丑寅卯辰巳午未申酉戌亥
子 1                               1
丑    1             1             1
寅       1 1    1 1    1 1    1
卯          1       1             1
辰             1    1    1       1
巳          1    1 1             1
午                   1             1
未          1 1 1 1 1 1 1    1
申                   1    1       1
酉          1    1 1    1 1    1
戌          1    1 1    1 1 1 1
亥                                  1
4
   子丑寅卯辰巳午未申酉戌亥
子 1                               1
丑    1             1             1
寅       1 1    1 1    1 1    1
卯          1       1             1
辰             1    1    1       1
巳          1    1 1             1
午                   1             1
未          1 1 1 1 1 1 1    1
申                   1    1       1
酉          1    1 1    1 1    1
戌          1    1 1    1 1 1 1
亥                                  1
   子丑寅卯辰巳午未申酉戌亥
子 1                               1
丑    1             1             1
寅       1 1    1 1    1 1    1
卯          1       1             1
辰             1    1    1       1
巳          1    1 1             1
午                   1             1
未          1 1 1 1 1 1 1    1
申                   1    1       1
酉          1    1 1    1 1    1
戌          1    1 1    1 1 1 1
亥                                  1
   子丑寅卯辰巳午未申酉戌亥
子 1                               1
丑    1             1             1
寅       1 1    1 1    1 1    1
卯          1       1             1
辰             1    1    1       1
巳          1    1 1             1
午                   1             1
未          1 1 1 1 1 1 1    1
申                   1    1       1
酉          1    1 1    1 1    1
戌          1    1 1    1 1 1 1
亥                                  1
5
   子丑寅卯辰巳午未申酉戌亥
子 1                               1
丑    1             1             1
寅       1 1    1 1    1 1    1
卯          1       1             1
辰             1    1    1       1
巳          1    1 1             1
午                   1             1
未          1 1 1 1 1 1 1    1
申                   1    1       1
酉          1    1 1    1 1    1
戌          1    1 1    1 1 1 1
亥                                  1

逐次平法法进行布尔乘积的次数虽然要少于自乘的方式，但是由于中间矩阵中值为1的个数更多，所以整个获得可达矩阵的时间效率上来说，它不一定快，甚至更慢！，只有改进为集合求解方式，其效率会大大加快


下图为它们的可达集合标记法，链表标识方式

矩阵相乘的次数 相乘矩阵自乘的方法 幂乘的方法 快速Warshall转移法
1
子 子、亥、
丑 丑、午、
寅 寅、巳、酉、
卯 卯、午、
辰 辰、申、
巳 卯、巳、
午 午、亥、
未 辰、未、酉、
申 午、申、
酉 巳、申、酉、
戌 酉、戌、
亥 亥、
子 子、亥、
丑 丑、午、
寅 寅、巳、酉、
卯 卯、午、
辰 辰、申、
巳 卯、巳、
午 午、亥、
未 辰、未、酉、
申 午、申、
酉 巳、申、酉、
戌 酉、戌、
亥 亥、
子 子、亥、
丑 丑、午、
寅 寅、巳、酉、
卯 卯、午、
辰 辰、申、
巳 卯、巳、
午 午、亥、
未 辰、未、酉、
申 午、申、
酉 巳、申、酉、
戌 酉、戌、
亥 亥、
2
子 子、亥、
丑 丑、午、亥、
寅 寅、卯、巳、申、酉、
卯 卯、午、亥、
辰 辰、午、申、
巳 卯、巳、午、
午 午、亥、
未 辰、巳、未、申、酉、
申 午、申、亥、
酉 卯、巳、午、申、酉、
戌 巳、申、酉、戌、
亥 亥、
子 子、亥、
丑 丑、午、亥、
寅 寅、卯、巳、申、酉、
卯 卯、午、亥、
辰 辰、午、申、
巳 卯、巳、午、
午 午、亥、
未 辰、巳、未、申、酉、
申 午、申、亥、
酉 卯、巳、午、申、酉、
戌 巳、申、酉、戌、
亥 亥、
子 子、亥、
丑 丑、午、亥、
寅 寅、卯、巳、申、酉、
卯 卯、午、亥、
辰 辰、午、申、
巳 卯、巳、午、亥、
午 午、亥、
未 辰、巳、午、未、申、酉、
申 午、申、亥、
酉 卯、巳、午、申、酉、亥、
戌 卯、巳、午、申、酉、戌、亥、
亥 亥、
3
子 子、亥、
丑 丑、午、亥、
寅 寅、卯、巳、午、申、酉、
卯 卯、午、亥、
辰 辰、午、申、亥、
巳 卯、巳、午、亥、
午 午、亥、
未 卯、辰、巳、午、未、申、酉、
申 午、申、亥、
酉 卯、巳、午、申、酉、亥、
戌 卯、巳、午、申、酉、戌、
亥 亥、
子 子、亥、
丑 丑、午、亥、
寅 寅、卯、巳、午、申、酉、亥、
卯 卯、午、亥、
辰 辰、午、申、亥、
巳 卯、巳、午、亥、
午 午、亥、
未 卯、辰、巳、午、未、申、酉、亥、
申 午、申、亥、
酉 卯、巳、午、申、酉、亥、
戌 卯、巳、午、申、酉、戌、亥、
亥 亥、
子 子、亥、
丑 丑、午、亥、
寅 寅、卯、巳、午、申、酉、亥、
卯 卯、午、亥、
辰 辰、午、申、亥、
巳 卯、巳、午、亥、
午 午、亥、
未 卯、辰、巳、午、未、申、酉、亥、
申 午、申、亥、
酉 卯、巳、午、申、酉、亥、
戌 卯、巳、午、申、酉、戌、亥、
亥 亥、
4
子 子、亥、
丑 丑、午、亥、
寅 寅、卯、巳、午、申、酉、亥、
卯 卯、午、亥、
辰 辰、午、申、亥、
巳 卯、巳、午、亥、
午 午、亥、
未 卯、辰、巳、午、未、申、酉、亥、
申 午、申、亥、
酉 卯、巳、午、申、酉、亥、
戌 卯、巳、午、申、酉、戌、亥、
亥 亥、
子 子、亥、
丑 丑、午、亥、
寅 寅、卯、巳、午、申、酉、亥、
卯 卯、午、亥、
辰 辰、午、申、亥、
巳 卯、巳、午、亥、
午 午、亥、
未 卯、辰、巳、午、未、申、酉、亥、
申 午、申、亥、
酉 卯、巳、午、申、酉、亥、
戌 卯、巳、午、申、酉、戌、亥、
亥 亥、
子 子、亥、
丑 丑、午、亥、
寅 寅、卯、巳、午、申、酉、亥、
卯 卯、午、亥、
辰 辰、午、申、亥、
巳 卯、巳、午、亥、
午 午、亥、
未 卯、辰、巳、午、未、申、酉、亥、
申 午、申、亥、
酉 卯、巳、午、申、酉、亥、
戌 卯、巳、午、申、酉、戌、亥、
亥 亥、
5
子 子、亥、
丑 丑、午、亥、
寅 寅、卯、巳、午、申、酉、亥、
卯 卯、午、亥、
辰 辰、午、申、亥、
巳 卯、巳、午、亥、
午 午、亥、
未 卯、辰、巳、午、未、申、酉、亥、
申 午、申、亥、
酉 卯、巳、午、申、酉、亥、
戌 卯、巳、午、申、酉、戌、亥、
亥 亥、

比较求解过程中每一步矩阵值与上一个矩阵的变化


矩阵相乘的次数 相乘矩阵自乘的方法 逐次平方法 快速转移法，Warshall快速转移
1
   子丑寅卯辰巳午未申酉戌亥
子 1                               1
丑    1             1               
寅       1       1          1      
卯          1       1               
辰             1          1         
巳          1    1                  
午                   1             1
未             1       1    1      
申                   1    1         
酉                1       1 1      
戌                            1 1   
亥                                  1
   子丑寅卯辰巳午未申酉戌亥
子 1                               1
丑    1             1               
寅       1       1          1      
卯          1       1               
辰             1          1         
巳          1    1                  
午                   1             1
未             1       1    1      
申                   1    1         
酉                1       1 1      
戌                            1 1   
亥                                  1
   子丑寅卯辰巳午未申酉戌亥
子 1                               1
丑    1             1               
寅       1       1          1      
卯          1       1               
辰             1          1         
巳          1    1                  
午                   1             1
未             1       1    1      
申                   1    1         
酉                1       1 1      
戌                            1 1   
亥                                  1
2
子 丑 寅 卯 辰 巳 午 未 申 酉 戌 亥
子 1 　 　 　 　 　 　 　 　 　 　 1
丑 　 1 　 　 　 　 1 　 　 　 　 1
寅 　 　 11 　 1 　 　 1 1 　 　
卯 　 　 　 1 　 　 1 　 　 　 　 1
辰 　 　 　 　 1 　 1 　 1 　 　 　
巳 　 　 　 1 　 11 　 　 　 　 　
午 　 　 　 　 　 　 1 　 　 　 　 1
未 　 　 　 　 11 　 11 1 　 　
申 　 　 　 　 　 　 1 　 1 　 　 1
酉 　 　 　 1 　 11 　 11 　 　
戌 　 　 　 　 　 1 　 　 1 11 　
亥 　 　 　 　 　 　 　 　 　 　 　 1
子 丑 寅 卯 辰 巳 午 未 申 酉 戌 亥
子 1 　 　 　 　 　 　 　 　 　 　 1
丑 　 1 　 　 　 　 1 　 　 　 　 1
寅 　 　 11 　 1 　 　 1 1 　 　
卯 　 　 　 1 　 　 1 　 　 　 　 1
辰 　 　 　 　 1 　 1 　 1 　 　 　
巳 　 　 　 1 　 11 　 　 　 　 　
午 　 　 　 　 　 　 1 　 　 　 　 1
未 　 　 　 　 11 　 11 1 　 　
申 　 　 　 　 　 　 1 　 1 　 　 1
酉 　 　 　 1 　 11 　 11 　 　
戌 　 　 　 　 　 1 　 　 1 11 　
亥 　 　 　 　 　 　 　 　 　 　 　 1
子 丑 寅 卯 辰 巳 午 未 申 酉 戌 亥
子 1 　 　 　 　 　 　 　 　 　 　 1
丑 　 1 　 　 　 　 1 　 　 　 　 1
寅 　 　 11 　 1 　 　 1 1 　 　
卯 　 　 　 1 　 　 1 　 　 　 　 1
辰 　 　 　 　 1 　 1 　 1 　 　 　
巳 　 　 　 1 　 11 　 　 　 　 1
午 　 　 　 　 　 　 1 　 　 　 　 1
未 　 　 　 　 11 1 11 1 　 　
申 　 　 　 　 　 　 1 　 1 　 　 1
酉 　 　 　 1 　 11 　 11 　 1
戌 　 　 　 1 　 1 1 　 1 111
亥 　 　 　 　 　 　 　 　 　 　 　 1
3
子 丑 寅 卯 辰 巳 午 未 申 酉 戌 亥
子 1 　 　 　 　 　 　 　 　 　 　 1
丑 　 1 　 　 　 　 1 　 　 　 　 1
寅 　 　 11 　 11 　 11 　 　
卯 　 　 　 1 　 　 1 　 　 　 　 1
辰 　 　 　 　 1 　 1 　 1 　 　 1
巳 　 　 　 1 　 11 　 　 　 　 1
午 　 　 　 　 　 　 1 　 　 　 　 1
未 　 　 　 1 111 111 　 　
申 　 　 　 　 　 　 1 　 1 　 　 1
酉 　 　 　 1 　 11 　 11 　 1
戌 　 　 　 1 　 11 　 111 　
亥 　 　 　 　 　 　 　 　 　 　 　 1
子 丑 寅 卯 辰 巳 午 未 申 酉 戌 亥
子 1 　 　 　 　 　 　 　 　 　 　 1
丑 　 1 　 　 　 　 1 　 　 　 　 1
寅 　 　 11 　 11 　 11 　 1
卯 　 　 　 1 　 　 1 　 　 　 　 1
辰 　 　 　 　 1 　 1 　 1 　 　 1
巳 　 　 　 1 　 11 　 　 　 　 1
午 　 　 　 　 　 　 1 　 　 　 　 1
未 　 　 　 1 111 111 　 1
申 　 　 　 　 　 　 1 　 1 　 　 1
酉 　 　 　 1 　 11 　 11 　 1
戌 　 　 　 1 　 11 　 1111
亥 　 　 　 　 　 　 　 　 　 　 　 1
子 丑 寅 卯 辰 巳 午 未 申 酉 戌 亥
子 1 　 　 　 　 　 　 　 　 　 　 1
丑 　 1 　 　 　 　 1 　 　 　 　 1
寅 　 　 11 　 11 　 11 　 1
卯 　 　 　 1 　 　 1 　 　 　 　 1
辰 　 　 　 　 1 　 1 　 1 　 　 1
巳 　 　 　 1 　 11 　 　 　 　 1
午 　 　 　 　 　 　 1 　 　 　 　 1
未 　 　 　 1 111111 　 1
申 　 　 　 　 　 　 1 　 1 　 　 1
酉 　 　 　 1 　 11 　 11 　 1
戌 　 　 　 1 　 11 　 1111
亥 　 　 　 　 　 　 　 　 　 　 　 1
4
子 丑 寅 卯 辰 巳 午 未 申 酉 戌 亥
子 1 　 　 　 　 　 　 　 　 　 　 1
丑 　 1 　 　 　 　 1 　 　 　 　 1
寅 　 　 11 　 11 　 11 　 1
卯 　 　 　 1 　 　 1 　 　 　 　 1
辰 　 　 　 　 1 　 1 　 1 　 　 1
巳 　 　 　 1 　 11 　 　 　 　 1
午 　 　 　 　 　 　 1 　 　 　 　 1
未 　 　 　 1111111 　 1
申 　 　 　 　 　 　 1 　 1 　 　 1
酉 　 　 　 1 　 11 　 11 　 1
戌 　 　 　 1 　 11 　 1111
亥 　 　 　 　 　 　 　 　 　 　 　 1
子 丑 寅 卯 辰 巳 午 未 申 酉 戌 亥
子 1 　 　 　 　 　 　 　 　 　 　 1
丑 　 1 　 　 　 　 1 　 　 　 　 1
寅 　 　 11 　 11 　 11 　 1
卯 　 　 　 1 　 　 1 　 　 　 　 1
辰 　 　 　 　 1 　 1 　 1 　 　 1
巳 　 　 　 1 　 11 　 　 　 　 1
午 　 　 　 　 　 　 1 　 　 　 　 1
未 　 　 　 1111111 　 1
申 　 　 　 　 　 　 1 　 1 　 　 1
酉 　 　 　 1 　 11 　 11 　 1
戌 　 　 　 1 　 11 　 1111
亥 　 　 　 　 　 　 　 　 　 　 　 1
子 丑 寅 卯 辰 巳 午 未 申 酉 戌 亥
子 1 　 　 　 　 　 　 　 　 　 　 1
丑 　 1 　 　 　 　 1 　 　 　 　 1
寅 　 　 11 　 11 　 11 　 1
卯 　 　 　 1 　 　 1 　 　 　 　 1
辰 　 　 　 　 1 　 1 　 1 　 　 1
巳 　 　 　 1 　 11 　 　 　 　 1
午 　 　 　 　 　 　 1 　 　 　 　 1
未 　 　 　 1111111 　 1
申 　 　 　 　 　 　 1 　 1 　 　 1
酉 　 　 　 1 　 11 　 11 　 1
戌 　 　 　 1 　 11 　 1111
亥 　 　 　 　 　 　 　 　 　 　 　 1
5
子 丑 寅 卯 辰 巳 午 未 申 酉 戌 亥
子 1 　 　 　 　 　 　 　 　 　 　 1
丑 　 1 　 　 　 　 1 　 　 　 　 1
寅 　 　 11 　 11 　 11 　 1
卯 　 　 　 1 　 　 1 　 　 　 　 1
辰 　 　 　 　 1 　 1 　 1 　 　 1
巳 　 　 　 1 　 11 　 　 　 　 1
午 　 　 　 　 　 　 1 　 　 　 　 1
未 　 　 　 1111111 　 1
申 　 　 　 　 　 　 1 　 1 　 　 1
酉 　 　 　 1 　 11 　 11 　 1
戌 　 　 　 1 　 11 　 1111
亥 　 　 　 　 　 　 　 　 　 　 　 1

化学加平台
解释结构模型
感谢化学加提供单独服务器服务器！请大家多支持化学加平台，可以多介绍人关注化学加！
对解释结构模型在线计算有什么意见与建议请发电子邮件到， hwstu #sohu.com 把#替换成 @