LC: Graph Valid Tree - spiralgo/algorithms GitHub Wiki

Graph Valid Tree

The Essence:

Understanding what a tree is would assist in solving this problem: There are few conditions of a such a given graph being a tree. It must

• be acyclic,
• have n-1 edges for n nodes,
• be connected,
• satisfy the condition that no connected node should have the same root.

The second condition is always easy to check at the start by comparing the number of edges and the given number n. If it passes the test, this means that some edges of some unconnected components lead cycles. For the rest, there are two strategies:

1. Begin searching the graph from some node. If cycles are detected or the number of nodes counted is not n (implies disconnection), then the result is false.
2. Try uniting the sets of graphs using the edges. Any cycles imply disconnection or cycle within a connected graph.

Details:

The implementation of these approaches as well as further explanation can be found here: https://github.com/spiralgo/algorithms/pull/332