graph - Update the DFS algorithm so it can detect cycles -

given g = (v,e) , vertices colored blue/green, path in g called infinite if looks v1,v2,v3,.. , between every v(i), v(i+1), there line between them.

g called infinite blue if has blue vertices in path.

update dfs algorithm can called infinite blue.

well, in other words, path infinite need detect if there cycles, means if reach vertex in recursion stack, there cycle in tree.

so, based on algorithm here:

before checking infinite blue, how believe can check cycle in general:

in dfs-visit: between 7. , 8. i'll add:

else if color[v] = green //detected cycle.

now want upgrade blue vertices included.

so in dfs(g) edit line 2. "do colorsecond[u] <- white"

now every vertex have color field green/blue , colorsecond white - meaning still undetected.

line 6. replaced accordingly.

in dfs-visit(u)

line 1. replaced "colorsecond[u] <- grey"

line 5. if color[v] = blue , colorsecond[v] = white

between 7. , 8. write "else if color[v] = blue , colorsecond[v] = grey" "cycle detected"