BFS check if graph is a tree

And the last one required method is a bit simpler. Tree graph is a one-component acyclic graph, so you have to check first, if it is acyclic.

Acyclic

During BFS, you check vertices on different levels, until you find the end vertex. When traversing a tree, each time you check vertices that haven’t been visited yet. The cycle is detected when you check neighbors for the current node and at least one of them is visited - at this point you can approve that at least one cycle is detected.

Connectivity

After that, if the cycle is detected, return False, because one condition is already unsatisfied.

If cycle is not found, you should check the connectivity, and you can do it either:

• Call hasOneComponentFunction()

• Check the visited array directly

The second approach is much faster, and you don’t have to traverse again, like with calling hasOneComponent(). Return if all vertices are visited.