7,129
个编辑
更改
跳到导航
跳到搜索
第107行：
第107行： − + − + +
→传递闭包和传递约简
===传递闭包和传递约简===
===传递闭包和传递约简===
有向无环图的传递闭包可以通过<font color="#ff8000"> '''广度优先搜索''' </font>或<font color="#ff8000"> '''深度优先搜索''' </font>对每个节点测试可达性来构建。算法对于一个有着{{mvar|n}}个顶点和{{mvar|m}}条边的有向无环图的复杂度为{{math|''O''(''mn'')}}。<ref>{{harvtxt|Skiena|2009}}, p. 495.</ref>也可以使用<font color="#ff8000"> '''矩阵乘法算法 Matrix multiplication algorithm''' </font>中最快的<font color="#ff8000"> '''Coppersmith–Winograd算法'''</font>，其复杂度为{{math|''O''(''n''<sup>''2.3728639''</sup>)}}。这个算法理论上在<font color="#ff8000"> '''稠密图 Dense graph'''</font>中快过{{math|''O''(''mn'')}}。<ref>{{harvtxt|Skiena|2009}}, p. 496.</ref>
有向无环图的传递闭包可以通过<font color="#ff8000"> '''广度优先搜索''' </font>或<font color="#ff8000"> '''深度优先搜索''' </font>对每个节点测试可达性来构建。算法对于一个有着{{mvar|n}}个顶点和{{mvar|m}}条边的有向无环图的复杂度为{{math|''O''(''mn'')}}。<ref>Skiena, Steven S. (2009), The Algorithm Design Manual, Springer, p. 495, ISBN 978-1-84800-070-4.</ref>也可以使用<font color="#ff8000"> '''矩阵乘法算法 Matrix multiplication algorithm''' </font>中最快的<font color="#ff8000"> '''Coppersmith–Winograd算法'''</font>，其复杂度为{{math|''O''(''n''<sup>''2.3728639''</sup>)}}。这个算法理论上在<font color="#ff8000"> '''稠密图 Dense graph'''</font>中快过{{math|''O''(''mn'')}}。<ref>Skiena, Steven S. (2009), The Algorithm Design Manual, Springer, p. 496, ISBN 978-1-84800-070-4.</ref>
不论在哪种传递闭包算法中，那些被一条长度至少为2的路径所连接的顶点对，都可以和只有一条长度为1的路径所连接的顶点对区分开。由于传递约简包含后者，传递约简可以在和传递闭包相同的<font color="#ff8000"> '''渐进时间复杂度 Asymptotic computational complexity''' </font>中被构建。<ref>{{harvtxt|Bang-Jensen|Gutin|2008}}, p. 38.</ref>
不论在哪种传递闭包算法中，那些被一条长度至少为2的路径所连接的顶点对，都可以和只有一条长度为1的路径所连接的顶点对区分开。由于传递约简包含后者，传递约简可以在和传递闭包相同的<font color="#ff8000"> '''渐进时间复杂度 Asymptotic computational complexity''' </font>中被构建。<ref>Bang-Jensen, Jørgen; Gutin, Gregory Z. (2008), "2.3 Transitive Digraphs, Transitive Closures and Reductions", Digraphs: Theory, Algorithms and Applications, Springer Monographs in Mathematics, Springer, p. 38, ISBN 978-1-84800-998-1.</ref>
<br>
===闭包问题===
===闭包问题===