学步园

刚刚写了图的广度优先算法，现在完成深度优先算法DFS，color等的意义和上一篇一致，但f用于记录完成时间。

DFS
color = {}
pai = {}
d = {}
time = 0
f = {} # 记录完成时间
def DFS(G):
    for u in G.keys():
        color[u] = 'WHITE'
        pai[u] = 'NIL'
    time = 0
    for u in G.keys():
        if color[u] == 'WHITE':
            DFS_VISIT(u)

def DFS_VISIT(u):
    print u
    color[u] = 'GRAY' # White vertex u has just been discovered.
    global time
    time += 1
    d[u] = time
    for v in G[u]: # Explore edge(u, v).
        if color[v] == 'WHITE':
            pai[v] = u
            DFS_VISIT(v)
    color[u] = 'BLACK' # Blacken u; it is finished.
    time += 1
    f[u] = time

G = {'A':['B','C'],'B':['D'],'C':['E'],'D':['C','E'],'E':[]}