1
$\begingroup$

According to DFS algorithm for graph traversing:

DFS(G)
  for each v ∈ V (G)
      v.mark = false
  time = 0
  for each v ∈ G.V
      if not v.mark
         DFS-Visit(v)
DFS-Visit(v)
   v.mark = true
   time = time + 1
   v.d = time
   for each (v, w) ∈ E(G)
      if w.mark == false
              w.parent = v
              DFS-Visit(w)
   time = time + 1
   v.f = time

Where v.d and v.f are start and final meet time of vertex "v".
Question:
Why should we use v.d and v.f? I cannot see the impact of the time in the pseudo code.Its just been incrementing and intializing to something but haven't been used by any if or for condition.

$\endgroup$

1 Answer 1

1
$\begingroup$

Those markings give a pre-ordering and a post-ordering respectively. They are indeed not used by the DFS algorithm per se.

There are several applications, one of them being that the reverse post-order is a topological sort. It can help finding strongly connected components efficiently.

See here for some details.

$\endgroup$
3
  • $\begingroup$ If the goal is to only traversing the graph and nothing else,should we use starting and ending time? $\endgroup$
    – Nameless
    Commented Nov 24, 2021 at 9:38
  • $\begingroup$ @program_craft No, you can skip those if you just want to do a graph traversal (for example for testing connectivity in an undirected graph). The same can be said with the .parent marking. It can be used to find paths in the graph, but is not necessary for the graph traversal. However, the .mark is mandatory. $\endgroup$
    – Nathaniel
    Commented Nov 24, 2021 at 10:33
  • $\begingroup$ Thanks ,I wanted this. $\endgroup$
    – Nameless
    Commented Nov 24, 2021 at 10:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.