给邻接矩阵求可达性矩阵

邻接矩阵是指在图中，用一个矩阵来表示顶点之间的连接关系，其中矩阵中的元素表示从一个顶点到另一个顶点是否有边连接。对于一个有向图的邻接矩阵，可以通过矩阵的幂运算来求解其可达矩阵。

具体来说，设邻接矩阵为 $A$，则可达矩阵 $R$ 的元素 $r_{i,j}$ 可以通过以下递推式得到：

$$r_{i,j}=\begin{cases}
1, & i=j \text{ 或 } a_{i,j}=1 \\
\sum\limits_{k=1}^{n} r_{i,k}a_{k,j}, & \text{otherwise}
\end{cases}$$

其中，$n$ 是邻接矩阵的大小。上述递推式表示，如果 $i=j$ 或者 $i$ 到 $j$ 有一条边，则 $r_{i,j}=1$；否则，$r_{i,j}$ 就等于所有能够到达 $i$ 的顶点到 $j$ 的路径之和。

可以使用矩阵幂运算来高效地计算可达矩阵。设 $A^k$ 表示邻接矩阵 $A$ 的 $k$ 次幂，则可达矩阵 $R$ 可以通过以下式子计算：

$$R=\sum\limits_{k=0}^{\infty}A^k$$

这里的 $\infty$ 表示一个足够大的数，使得 $\sum\limits_{k=0}^{\infty}A^k$ 收敛。在实际应用中，通常使用矩阵快速幂算法来计算矩阵的幂，以提高计算效率。