白色路徑定理

白色路徑定理 在一個有向或無向圖G=(V,E)的深度優先森林中,結點v是結點u的後裔若且唯若在搜尋發現u的時刻d[u],從結點u出發經一條僅由白色結點組成的路徑可達v。 --- 《算法導論》。
在圖論中未染色的頂點(vertices)為白色,搜尋到該結點時為灰色,當搜尋完其相鄰結點時為黑色。這種染色也產生了時間戳的概念。

相關詞條

熱門詞條

聯絡我們