白色路徑定理

白色路徑定理

"在一個有向或無向圖G=(V

目錄

正文


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