Complex Networks

Algorithms and Complexity

 37

a

b c

d

f

e

g

h

1

4

5

6

7

83

9

10

11

2

12

13

14

Figure 3.6: DFS algorithm execution

node u as visited and recording its visit time. An integer variable time is incremented

each time a node v is visited whether first time or upon completion of the visits to all

neighbors of v.

Figure 3.6 displays the execution of DFS

forest algorithm in the same example

network Figure 3.5 where each node has the first and last visit times shown. There

is a single connected component in this graph and therefore the loop between lines 8

and 11 is executed once and the total time is 16.

The initialization of the DFS algorithm takes Θ(n) time as each vertex is consid- ...