← 返回卡片

原书出处

Introduction to Algorithms, Fourth Edition

35 第35章 近似算法

Fourth edition · 核验版本的摘录快照 · 导入于 2026-10-23T08:18:08.785Z

ializes C to the empty set. Line 2 sets E′ to be a copy of the edge set G.E of the graph.

The while loop of lines 3–6 repeatedly picks an edge (u, v) from E′, adds its endpoints u and v into C, and deletes all edges in E′ that u or v covers. Finally, line 7 returns the vertex cover C. The running time of this algorithm is O(V + E), using adjacency lists to represent E′. APPROX-VERTEX-COVER (G) 1 C = Ø 2 E′ = G.E 3

while E′ ≠ Ø 4 let (u, v) be an arbitrary edge of E′ 5 C = C ∪ {u, v} 6 remove from E′ ed

此预览只包含定位所需的摘录和上下文。

原书定位详情

来源:a19c7933-4eda-4176-aebd-30fe7e1ad292

正文位置:extracted/Introduction to Algorithms, Fourth Edition/_epub-src/OEBPS/chapter035.xhtml

EPUB SHA-256:ec7ced04bb875b93983816aef7a667855a4b71c5cf53b63406b9439c74e27aea