有向图邻接矩阵幂的意义

邻接矩阵的记录

邻接矩阵分为两种：

①:存的是边权（记作$D$），

即

②：没有边权的， 记录的是连通关系（记作$A$），

即

连通关系的邻接矩阵幂的意义：

设表示一个有向图的连通关系的邻接矩阵为$A$，在$A$中的元素$A_{i,j}$如果为1，那么表示原图中点$i$,点$j$之间通过一条长度为$1$的边直接相连，那么$A^k$中的$A^k_{i,j}$表示点点$i$,点$j$之间能通过$k$条边相连。感性理解一下还是能够理解的。。。

举个例子吧,先去大佬的blog中借用例子。。。https://blog.csdn.net/u010504064/article/details/39781709?utm_source=blogxgwz0

在平方后我们依然得到了一个二维矩阵，其中的每个元素值的含义是以有向图中节点的直接邻接点是否可达为准。

用图描述

图1 有向图

图2 有向图的邻接矩阵表示  

图 3有向图的平方后的矩阵

      就是以1节点的邻接点2为准，这个邻接点所有的邻接点3，也就是说图3中第一行第三个元素的值为1表示1节点可以通过它的邻接点2访问到3，同理第二行最后一个元素为1表示节点2可以通过3访问到4，,当然元素为0表示该节点不能间接到达，当元素值为1表示有一条路径可以到达，元素值为2的时候有两条路径可以到达。

那么$A^k$的意义是什么？（两个点之间若有边则$A[u][v]=1$）

从$Floyd$算法的角度考虑，不难发现$A^k$的第$i$行第$j$列的数字含义是从$i$到$j$经过$k$步的路径方案总数。

 习题：

　　Luogu 3758 [TJOI2017]可乐：https://www.luogu.org/problemnew/show/P3758

　　解题思路：https://www.cnblogs.com/Dxy0310/p/9840451.html