Kosaraju

释义 Definition

Kosaraju 通常指 Kosaraju 算法（Kosaraju’s algorithm）：一种在有向图中寻找强连通分量（Strongly Connected Components, SCC）的经典算法，核心思路是对原图与反向图各进行一次深度优先搜索（DFS），以线性时间复杂度 O(V + E) 计算 SCC。（该词也可指提出该算法的计算机科学家 S. Rao Kosaraju。）

发音 Pronunciation (IPA)

/ˌkoʊsəˈrɑːdʒuː/

例句 Examples

Kosaraju’s algorithm finds strongly connected components in a directed graph.
Kosaraju 算法用于在有向图中找出强连通分量。

After finishing DFS on the reversed graph, Kosaraju processes nodes in decreasing finish time to extract each SCC efficiently.
在反向图上完成 DFS 后，Kosaraju 会按完成时间从大到小处理节点，从而高效地提取每个强连通分量。

词源 Etymology

Kosaraju 来自人名 S. Rao Kosaraju（印度裔计算机科学家）。该算法以提出者命名，在算法与图论教学中常与 Tarjan、Gabow 等 SCC 算法并列出现。

相关词 Related Words

• Algorithm
• Graph
• Directed
• Vertex
• Edge
• DFS
• SCC
• Tarjan
• Topological

文献与作品 Notable Works

• Introduction to Algorithms（Cormen, Leiserson, Rivest, Stein，俗称 CLRS）——在强连通分量与图算法相关章节/习题体系中常提及 Kosaraju 思路或与其他 SCC 方法对照讲解。
• Algorithms（Robert Sedgewick & Kevin Wayne）——在有向图、DFS 与强连通分量部分常介绍 Kosaraju-Sharir 算法。
• 经典论文与讲义中常见 “Kosaraju–Sharir algorithm” 表述（强调其在教学与实现中的标准化版本）。