知识卡片
传递闭包记录所有可达顶点对
有向图的传递闭包保留原顶点,并对每个存在路径的有序顶点对(i,j)加入一条边。
它只回答可达性,不需要路径长度或边权。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第23章 所有结点对的最短路径 · 查看原书依据
We define the transitive closure of G as the graph G* = (V, E*), where E* = {(i, j) : there is a path from vertex i to vertex j in G}. One way to compute the transitive closure of a graph in Θ(n3) time is to assign a
参考来源
- 位置:《算法导论(第4版)》第23章《所有结点对的最短路径》(OEBPS/chapter023.xhtml,文本字符[20000,25000))。
- 结论依据:原文明确闭包边集由存在路径的顶点对组成。
- 原始内容:We define the transitive closure of G as the graph G * = ( V , E *), where E * = {( i , j ) : there is a path from vertex i to vertex j in G }. One way to compute the transitive closure of a graph in Θ( n 3 ) time is to assign a