头悬梁锥刺股的主人公:Warshall算法
来源:百度文库 编辑:查人人中国名人网 时间:2024/09/02 23:05:27
Warshall算法的定义是什么?
举例说明Warshall算法
举例说明Warshall算法
Warshall算法是计算稠密有向图的传递闭包的首选。
通过计算传递闭包后,可以测试有向图中任何顶点是否可以从其它顶点到达的能力。
经典形式
for(i=0;i<V;++i)
for(s=0;s<V;++s)
for(t=0;t<V;++t)
if(A[s][i] && A[i][t]) A[s][t]=1;
用接邻矩阵A表示有向图,可以定义为 bool A[V][V];
V是A中的总结点数
A[i][j]=1表示从i到j有一条边,
A[i][j]=0表示i到j没有边;