Solution Review: Check if a Directed Graph is Tree or not

Statement

Given an undirected graph containing $n$ nodes labeled from $0$ to $n - 1$, determine whether the graph is a valid tree or not. Return TRUE if the edges of the given graph make up a valid tree, and FALSE otherwise.

A graph is a valid tree when all the nodes are connected and there is no cycle between them.

Constraints:

Let $n$ be the number of nodes in the undirected graph, where:

• $1 \leq$ $n$ $\leq 10^2$

• $0 \leq$ $edges$ $\leq 5 \times 10^3$

• There are no repeated edges

• There are no self-loops

Solution

To check if the graph is a valid tree, we start from the first node and move to adjacent nodes using a depth-first search. We mark visited nodes and look for cycles by checking if a node has been visited before. If we encounter a previously visited node that is not the parent, we have found a cycle, indicating the graph is not a tree. If the depth-first search started from the first node is complete, but some nodes remain unvisited, the graph is not connected, making it not a tree. If all nodes have been visited and no cycles are found, the graph is a valid tree.

The following are the steps of the algorithm:

• Initialize a visited list to keep track of nodes that will be visited during the traversal of the graph.

• Starting from the first node, start traversing adjacent nodes in the graph.

• While traversing the adjacent nodes in the graph, mark the current node as visited in the visited list.

• Pick an adjacent node and check if the node has been visited before.

  • If a node has not been visited before, continue the traversal from this node.

  • Otherwise, if the node has been visited before and is not the parent of the current node, a cycle has been found. Return FALSE.

• After completing the depth-first search, traverse the visited list and check if the value of any index is FALSE; it means the graph is disconnected, return FALSE. Otherwise, if all values are TRUE, return TRUE, indicating the graph is a tree.

The following illustration demonstrates the algorithm: