← 返回刚才阅读的位置

知识卡片

问题卡 · 5654.d.1.f.3.w · 生成模型:未记录

图转置不能丢掉孤立顶点

理解等级:中级

有向图转置Gᵀ保留同一个顶点集,只将每条u→v改成v→u。若只按原书答案遍历边并为端点插顶点,就会漏掉没有任何边的孤立顶点;E=0时甚至得到空图,不满足定义。

完整思路需先保证所有V个顶点都被保留,再逐边反向插入。复用同一顶点对象时还要约定哪一张图拥有数据,避免两个destroy都释放同一对象。

成本取决于表示:本章每次插顶点/边含O(V)查找,先插全顶点可能O(V²),反向插边O(VE),共可写O(V²+VE)。若有现成直接顶点索引,才可能按一次扫描O(V+E)构造。后者是另一表示条件,不是此答案已实现的成本。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • · 查看原书依据

      图的转置是指将该图的边反转。正式的说法是,对于一个有向图G=(V,E),它的转置记为GT。假设采用邻接表表示方式,该如何实现图的转置?该操作的时间复杂度是什么? 答:要实现图G=(V,E)的转置GT,遍历V中每个顶点的邻接表。遍历过程中要确保针对每个顶点通过调用graph_ins_vertex将顶点

    参考来源

    - 位置:《算法精解:C语言描述》第11章《问与答》(spine1334;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1301.html;u201-ch11-024)。 - 结论依据:201转置完整问答实读,原答案按2E次端点插入遗漏孤立点,由Gᵀ顶点集不变定义直接纠正;成本包含修正后新增的全顶点阶段,未运行。 - 原始内容:图的转置是指将该图的边反转。正式的说法是,对于一个有向图G=(V,E),它的转置记为GT。假设采用邻接表表示方式,该如何实现图的转置?该操作的时间复杂度是什么? 答:要实现图G=(V,E)的转置GT,遍历V中每个顶点的邻接表。遍历过程中要确保针对每个顶点通过调用graph_ins_vertex将顶点