传递还原算法：伪code？ [英] transitive reduction algorithm: pseudocode?

问题描述

我一直在寻找一种算法来执行上图的传递减少，但没有成功。有没有在我的算法圣经（算法导论由Cormen等），并同时我见过很多传递闭伪code，我一直无法追查任何的降低。我得到的最接近的是，有一个在Algorithmische Graphentheorie由沃尔克图罗夫（ISBN：978-3-486-59057-9），但不幸的是我没有获得这本书！维基百科是无益的，谷歌还没有发现任何。 ：^（

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?

推荐答案

见哈利许。 算法查找有向图的最小等价的图形。，ACM学报，22（1）：11-16，1975年1月的简单立方的算法如下（使用N×N个路径矩阵）足以满足的DAG，但许推广到循环图。

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;

这篇关于传递还原算法：伪code？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！