首页 > 试题广场 >

证明:使用单个位来存放每个节点的颜色已经足够,这一点可以通过

[问答题]
证明:使用单个位来存放每个节点的颜色已经足够,这一点可以通过证明如下事实来得到:如果将DFS-VISIT的第2行删除,DFS给出的结果相同。
DFS(G){
    for u in G.V
        u.color = white
        u.p = NIL
    time = 0
    for u in G.V
        if u == white
            DFS-VISIt(G,u)
}
DFS-VISIT(G,u){
    time ++
    u.d = time
    u.color = gray
    for v in G.Adj[u]
        if v.color == white
            v.p = u
            DFS-VISIT(G,v)
    u.color = black
    time ++
    u.f = time
}


这道题你会答吗?花几分钟告诉大家答案吧!