可达矩阵_数学名词 - 线报百科mbji.cn

可达矩阵

数学名词

可达矩阵，指的是用矩阵形式来描述有向图的各节点之间经过一定长度的通路后可达到的程度。可达矩阵的计算方法是利用布尔矩阵的运算性质。

可达矩阵

是用矩阵形式来描述有向连接图各节点之间经过一定长度的通路后可达到的程度。

在实际系统建模工程中，有向图D={S,R}中，对于Si,Sj 属于S，如果从Si到Sj有任何一条通路存在，则可称Si可达Sj。

利用布尔矩阵的运算性质给出了计算有向图可达矩阵的方法,该方法计算简便.

对于可达矩阵求解方法有如下几种方式：

1、连乘法：

其中A为原始邻接布尔矩阵，I为单位矩阵，R为可达矩阵

2、幂乘法：

通过转移矩阵的方式计算出可达矩阵

4、迭代warshall算法

对每个要素进行warshall操作后，记录其状态，下个要素迭代时候是以当前状态为基础进行迭代

5、tarjan算法求出所有强连通分量后一次性迭代warshall算法即可

上述五种方法中，最后一种方法比前面四种方法运算速度上有数量级的提高。对于普通的100*100的邻接矩阵，其速度大致提高100倍左右。

参考资料

最新修订时间：2023-02-09 13:25

条目作者

概述

参考资料