educative.io

I'm confused when comparing challenge 7 to challenge 3, why does challenge 3 need to use a recursive function on every vertex (line9-line11) to detect a cycle while challenge 7 doesn't?


#1

To understand why each vertex needs to be checked in Challenge 3, we have to look at a vital difference between graphs and trees. Graphs do not have have to be fully connected like trees. Consider the following graph which has 6 nodes:

0 -> 1 -> 2

3 -> 4 -> 5 -> 3 (This subgraph has a loop)

As we can see, the graph comprises of two subgraphs. If the recursive call is done on any of the nodes in the first subgraph, the algorithm will return false. Yet, the graph as a whole has a loop in it so it should return true. This is why we would have to check the connectivity of each vertex. This will ensure that no subgraph is missed. Such a problem does not occur with trees since all the nodes are connected.