可达矩阵

⼀种使⽤Python计算可达矩阵的简单⽅法

在进⾏编码前要简单介绍⼏个知识点：有向图，邻接矩阵，可达矩阵

有向图、邻接矩阵、可达矩阵

有向图

现实中常常会表⽰从⼀个地点到另⼀个地点的路径，这样的带有从起点到终点的路线表⽰可以⽤有向图表⽰。如下图所⽰：

在该图中，可以看成由地点F1到F2，以及F1到F3,F3到F2的路径。

这种有向图也表⽰两个因素的相互影响关系，再结合上⾯的有向图，我们可以理解为因素F1对因素F2有影响，对F3也有影响，因素F3对

F2也有影响。

邻接矩阵

邻接矩阵内的元素表⽰两两元素之间的关系，在邻接矩阵中，矩阵[i,j]表⽰从Fi可以直接到达Fj,或者Fi可以直接影响Fj。

再看上图，F1,F2,F3之间的邻接矩阵为：

在该邻接矩阵中，1表⽰可以直接影响，或者直接到达，0表⽰不可影响或不可到达。

邻接矩阵的元素进⾏运算遵循以下规则：

可达矩阵

可达矩阵中的元素表⽰从⼀个地点到另⼀个地点是否存在⼀个路径，或者⼀个因素到另⼀个因素是否有影响路径。

可达矩阵可由邻接矩阵得到，得到的⽅法有如下规则：

假设有邻接矩阵A,以及单位矩阵I(I和A的维度是相同的),则对两进⾏进⾏(A+I)运算，当满⾜如下关系时：

则M就是求出来的可达矩阵。

代码测试部分

其实这种利⽤邻接矩阵求可达矩阵的运算就是简单的与或运算，⽹上有很多代码都是根据与或运算来得到的，但是可以有另外⼀种思路，就

是在总结上述矩阵时，先使⽤传统的矩阵运算获得矩阵，在获得新矩阵时，先对矩阵进⾏处理，处理逻辑为：若元素值⼤于或等于1，则该

元素就是1，如果是0，则就是0，不管它。我的代码就是这种思想。

我们采⽤了⽹上有答案的⼀个邻接矩阵进⾏测试，原矩阵为：

可以看出已经将邻接矩阵和单位矩阵进⾏了初步的处理。

求可达矩阵简单代码如下：

#使⽤numpy包

importnumpyasnp

relat_matrix=([[1,0,1,1,1,0,0],[0,1,0,0,0,1,1],[0,1,1,0,0,0,0],[0,1,0,1,0,0,0],[0,0,0,0,1,1,0],[0,0,0,0,0,1,1],[0,0,0,0,0,0,1]])

#第K+1步更新的矩阵

new_matrix=relat_matrix

#第K步的更新的矩阵

old_matrix=new_matrix

#进⾏循环终⽌的判断条件

m=0

#统计运算的步骤K

step=1

whilem==0:

old_matrix=new_matrix

new_matrix=old_matrix*relat_matrix

foriinrange(0,len(new_matrix)):

forjinrange(0,len(new_matrix)):

#如果元素⼤于1，就输出为1

if(new_matrix[i,j]>=1):

new_matrix[i,j]=1

step=step+1

print(step)

#判断K次更新的矩阵和K+1次更新的矩阵是否相等

if(old_matrix==new_matrix).all():

#如果相等，终⽌循环，让m=1,并输出结果

m=1

print(new_matrix,step)

输出结果为：

从上述的运⾏结果可以看出，总共在运⾏到K=4的时候便得到了想要的可达矩阵，并将可达矩阵输出到界⾯上，与原推理的最终结果如下图

是相同的。