Depth-First Search

Depth-first search animation

function DepthFirstSearch(G) {
    for each vertex u in G.V {
        u.color = white
        u.phi= NaN
    }
    time = 0
    //Step = 0
    for each vertex u in G.V {
        if (u.color is white) {
            VisitNext(G, u)
        }
    }
}

function VisitNext(G, u) {
    time=time+1 
    u.d=time
    u.color= grey
    //Step++
    for each v in G.AdjacencyList[u] {
        if (v.color is white) {
            v.phi=u
            VisitNext(G,v)
        }
    }
    u.color= black
    time=time+1
    u.f=time
    //Step++
}

Task 1 Step by step depth-first search

Visualize the process of depth-first search -- color and distance change of each vertex. The check points are marked as Step++ in the pseudocode.

The input graph G is shown below.

Click on vertex to edit. Pay attention on the order in each adjacency list and the vertex storage order!

Task 2 Fill in the distance and predecessor table

Show the d and phi values that result from running depth-first search on this directed graph, using vertex u as the source.

The input graph G is shown below.