Question

Consider a modification to the DFS procedure such that it returns for an undirected graph
G, the connected components of G. To do this, you will modify the DFS procedure to
• maintain a counter i, initially set in 1, that counts how many connected components we found so
far; and
• on each vertex v ∈ G.V maintain an attribute component indicating to which connected component
number v belong to. That is, when DFS terminates, v.component indicates the component number
1, 2, . . . i that v belongs to.
Answer the following questions:
(a) Write the pseudocode for this slightly modified version of the DFS algorithm
(b) Explain why your algorithm is correct and its running time. You do not need to provide a formal
argument for correctness, but be sure to explain in clear terms.

Answer 1

we will have variable count=1 which would count the number of connected components

apart from count we also create an array component[] of size |V|, where component[i] would store the component in which node i lies.

Algorithm:

procedure DFS_modified(G) is

count =1;

component[i]=1 for each i

    let S be a stack and v be a non-discovered vertex
    S.push(v)
    component[v]=count               
    while S is not empty do
        v = S.pop()
        if v is not discovered yet then
            mark v as discovered
            for all each neighbour w of v do
                S.push(w)

                              component[w]=count;             // assign each w the same component number as its parent

        count++;                                                       //increase the component count

The running time is same as regular DFS i.e. O(m+n)

The correctness follows from th efact that child of each node should be in same component. and that is what algorithm does, it asigns the same component number to child as node's