传递归约算法:伪代码? [英] transitive reduction algorithm: pseudocode?
问题描述
我一直在寻找一种算法来对图执行传递归约,但没有成功.我的算法圣经中没有任何内容(Cormen 等人的算法简介),虽然我已经看到了大量的传递闭包伪代码,但我无法找到任何减少的东西.我得到的最接近的是 Volker Turau (ISBN:978-3-486-59057-9) 的Algorithmische Graphentheorie"中有一个,但不幸的是我无法访问这本书!维基百科没有帮助,谷歌还没有出现任何东西.:^(
I have been looking for an algorithm to perform a transitive reduction on a graph, but without success. There's nothing in my algorithms bible (Introduction To Algorithms by Cormen et al) and whilst I've seen plenty of transitive closure pseudocode, I haven't been able to track down anything for a reduction. The closest I've got is that there is one in "Algorithmische Graphentheorie" by Volker Turau (ISBN:978-3-486-59057-9), but unfortunately I don't have access to this book! Wikipedia is unhelpful and Google is yet to turn up anything. :^(
有人知道执行传递归约的算法吗?
Does anyone know of an algorithm for performing a transitive reduction?
推荐答案
见 Harry Hsu.一种寻找有向图的最小等效图的算法.",ACM 杂志,22(1):11-16,1975 年 1 月.下面的简单三次算法(使用 N x N 路径矩阵)足以满足 DAG,但 Hsu 将其推广到循环图.
See Harry Hsu. "An algorithm for finding a minimal equivalent graph of a digraph.", Journal of the ACM, 22(1):11-16, January 1975. The simple cubic algorithm below (using an N x N path matrix) suffices for DAGs, but Hsu generalizes it to cyclic graphs.
// reflexive reduction
for (int i = 0; i < N; ++i)
m[i][i] = false;
// transitive reduction
for (int j = 0; j < N; ++j)
for (int i = 0; i < N; ++i)
if (m[i][j])
for (int k = 0; k < N; ++k)
if (m[j][k])
m[i][k] = false;
这篇关于传递归约算法:伪代码?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!