可达矩阵算法的原理是什么？ 第1页
1
kong-long-90-55 网友的相关建议:
设图G的结点集合 ，其邻接矩阵
和 不直接相连，那么每条从 到 的长度为2的路，中间必然经过1个结点 。
即
如果图中有这样一个路存在，那么 ，即
反之，如果不存在这样的路，那么 或者 ，即
于是，结点 到 的路的数目为：
恰好等于 中第 行第 列的元素。
故按数字算， 每元素就是长度为2的路的数目，同理， 就是长度为 的路的数目。
按布尔值算，就是可达和不可达了。
1
相关话题
请问对称矩阵的平方根怎么算，有公式吗？为什么矩阵内积的定义包含一个迹运算？
有哪些有趣的矩阵？
红黑树的实现可以有多精简（各种语言随意）？
戴克斯特拉算法（Dijkstra）的本质是贪心，还是动态规划？
算法岗诸神黄昏，算法初级职位内卷，如何选择适合自己的方向?
矩阵P和矩阵Q的秩相等为t，那么拼在一起的矩阵(P,Q)的秩是否为t？为什么？
一个算法面试题，怎么写？
如何评价百度自动驾驶 ApolloAuto 在 Github 上发布的代码？
为什么得不到「自由意志」会让那么多人难以接受？
前一个讨论
布尔代数是怎么出现的？
相关的话题
python怎么去掉最大值和最小值，怎么找到最大值与最小值，去掉最大值最小值比如下面这道题?n - r = 基础解系的个数，这是为什么？
公民身份号码有可能是素数吗？
各种机器学习算法的应用场景分别是什么（比如朴素贝叶斯、决策树、K 近邻、SVM、逻辑回归最大熵模型）？
什么是 hash？
刚进算法团队，大牛们讨论高深的 cv 术语和算法，如何才能听懂？
有没有手算根号pi的方法？
为什么技术主管跟我说程序员学算法不是最重要的，从工作项目中学习实际才是最重要的？
矩阵乘法的本质是什么？
李亚普诺夫第一法（小干扰法）判断系统稳定性为什么当状态矩阵出现零根或实部为 0 的虚根的时候会失效？
如何判断这两份代码的时间复杂度？
如何评价教育部发文：AI、算法等2018年进入全国高中课程？
cv/nlp等方向的就业困难是全球性的吗？
类似微博的 feed 热度算法如何计算？
程序员必须掌握哪些算法？
计算机行业是不是自砸饭碗的行业？
李亚普诺夫第一法（小干扰法）判断系统稳定性为什么当状态矩阵出现零根或实部为 0 的虚根的时候会失效？
你写过什么有趣的程序？
如何理解矩阵相乘的几何意义或现实意义？
美团公开外卖订单分配算法，详解算法如何判断一个骑手的时间宽裕程度和顺路程度，有哪些值得关注的信息？
一个关于拓扑排序的扩展问题，可以做到的最优复杂度是？
1/3+1/6=计算机是如何得出0.5的?
如何面对算法竞赛的焦虑？
计算复杂性理论是否具有足够的现实意义，如今有哪些比较「现实」的应用？
向量组等价时其秩一定想等吗？
如何证明一个数 n 的因子之和是 O(n) 的？
如何看待两次 IOI 金牌，一次 ACM 全球总决赛亚军的清华大学计算机系毕业生去高中当信息学教师？
1/3+1/6=计算机是如何得出0.5的?
一个算法面试题，怎么写？
如何用简单易懂的例子解释隐马尔可夫模型？