知识卡片

普通读书笔记卡 · 3663

传递闭包记录所有可达顶点对

理解等级:中级

有向图的传递闭包保留原顶点,并对每个存在路径的有序顶点对(i,j)加入一条边。

它只回答可达性,不需要路径长度或边权。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《算法导论(第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