Solution: Graph Valid Tree

Let's solve the Graph Valid Tree problem.

We'll cover the following

Statement

Given an undirected graph containing nn nodes labeled from 00 to n−1n - 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 nn be the number of nodes in the undirected graph, where:

  • 1≤1 \leq nn ≤102 \leq 10^2

  • 0≤0 \leq edgesedges ≤5×103\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:

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.