22.3-10

[stslxg]

In undirected graphs, essentially each edge (u,v) appears twice, once in the adjacency list of u, once in that of v. If you use the same algorithm directly, you will print each tree edge twice (once as a tree edge and once as a back edge). So if v's color is gray, you still need to check if v is u's parent. If so, you shouldn't print the edge (u,v) as a back edge. You will also print a back edge twice (once as a back edge and once as a "forward" edge). To avoid this we need to ignore (u,v) if v is black, since we won't really have forward or cross edges. So I think for undirected graph we should use the following code:

DFS-VISIT-PRINT(G, u)
    time = time + 1
    u.d = time
    u.color = GRAY
    for each vertex v ∈ G.Adj[u]
        if v.color == WHITE
            print "(u, v) is a tree edge."
            v.π = u
            DFS-VISIT-PRINT(G, v)
        else if v.color == GRAY and v != u.π
            print "(u, v) is a back edge."
    u.color = BLACK
    time = time + 1
    u.f = time