387
个编辑
更改
跳到导航
跳到搜索
第71行：
第71行： − + − +
→传递闭包和传递约简
=== 传递闭包和传递约简 ===
=== 传递闭包和传递约简 ===
有向无环图的传递闭包可以通过[[广度优先搜索|广度优先搜索]]或[[深度优先搜索]]对每个节点测试可达性来构建。算法对于一个有着{{mvar|n}}个顶点和{{mvar|m}}条边的有向无环图的复杂度为{{math|''O''(''mn'')}}。<ref>{{harvtxt|Skiena|2009}}, p. 495.</ref>也可以使用{{tsl|en|matrix multiplication algorithm|矩阵乘法算法}}中最快的<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>{{harvtxt|Skiena|2009}}, p. 495.</ref>也可以使用{{tsl|en|matrix multiplication algorithm|矩阵乘法算法}}中最快的<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>
不论在哪种传递闭包算法中，那些被一条长度至少为2的路径所连接的顶点对，都可以和只有一条长度为1的路径所连接的顶点对区分开。由于传递约简包含后者，传递约简可以在和传递闭包相同的{{tsl|en|Asymptotic computational complexity|渐进时间复杂度}}中被构建。<ref>{{harvtxt|Bang-Jensen|Gutin|2008}}, p. 38.</ref>
不论在哪种传递闭包算法中，那些被一条长度至少为2的路径所连接的顶点对，都可以和只有一条长度为1的路径所连接的顶点对区分开。由于传递约简包含后者，传递约简可以在和传递闭包相同的<font color="#ff8000"> 渐进时间复杂度 Asymptotic computational complexity </font>中被构建。<ref>{{harvtxt|Bang-Jensen|Gutin|2008}}, p. 38.</ref>
=== 闭包问题 ===
=== 闭包问题 ===