Warshell算法

目的

快速找出一个顶点是否可以从其他顶点到达

原理

  1. 检查邻接矩阵的连通性,通过系统的修改邻接矩阵得到。原图传递闭包
  2. 邻接矩阵中:行号代表从哪里开始,列号代表边到哪里结束
  3. 基于合并路径(多个1步,变为一个多步)

Sample

  1. A->C,矩阵A行C列值为1;
  2. B->A,矩阵B行A列值为1;
  3. B->A->C,矩阵B行C列值为1(在矩阵中赋值为1);
  4. 这样邻接矩阵中即可以快速查找到B->C的路径为1.

算法

  1. 先遍历A行,直到早M列查找到1;
  2. 遍历A列,直到某N查找到1;
  3. 对N行M列赋值为1,表明路径存在。

实现

  1. 第一个while循环遍历所有的行;(遍历矩阵中所有的行)
  2. 第二个while循环遍历当前行中所有的列;(查找A->C)
  3. 第三个while循环遍历第一个while行所对应的列;(查找B->A)