time is counted twice in dfs?

[davyzhu]

time is counted twice in dfs, is it an intentional behavior? Thanks!

In regular-tree-dfs-demo-out

entered vertex 1 at time 2
tree edge (1,3)
entered vertex 3 at time 4
tree edge (3,7)

In bfs-dfs.c

void dfs(graph *g, int v) {
   ...
    discovered[v] = true;
    time = time + 1;
    entry_time[v] = time;

    process_vertex_early(v);
   ...

In dfs-demo.c

void process_vertex_early(int v) {
    time = time + 1;
    entry_time[v] = time;
    printf("entered vertex %d at time %d\n",v, entry_time[v]);
}

[SkienaBook]

Thanks for your comments.

I am not going to call this an errata, because the use of the time variable is to compare whether event A is before B, and generally the exact value of the time (it being from 1 to 2n) is irrelevant.

Steven Skiena

On Tue, May 11, 2021 at 5:37 AM Zhu, Shenli @.***> wrote:

time is counted twice in dfs, is it an intentional behavior? Thanks!

In regular-tree-dfs-demo-out

entered vertex 1 at time 2 tree edge (1,3) entered vertex 3 at time 4 tree edge (3,7)

In bfs-dfs.c

void dfs(graph *g, int v) { ... discovered[v] = true; time = time + 1; entry_time[v] = time;

process_vertex_early(v);

...

In dfs-demo.c

void process_vertex_early(int v) { time = time + 1; entry_time[v] = time; printf("entered vertex %d at time %d\n",v, entry_time[v]); }

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/SkienaBook/Algorithm-Design-Manual-Programs-V3/issues/1, or unsubscribe https://github.com/notifications/unsubscribe-auth/AOHR7254QQGEAVAGJUNU6ILTND3HLANCNFSM44U5AJ5A .