计算有向图的可达矩阵的算法及其MATLAB实现

算法思想

设A为n阶有向图的邻接矩阵

先求出Bn=A+A2+⋅⋅⋅+An

然后把矩阵Bn的不为0的数变为1，为0的数不变

MATLAB实现

function P = dgraf(A)n = size(A,1);P = A;for i = 2 : nP = P + A^i;endP(P ~= 0) = 1;

测试

测试用例： A = [0,1,1,1;1,0,1,1;1,1,0,1;1,1,1,0];

测试结果：ans =

1111111111111111