Solution: Graph Valid Tree
Let's solve the Graph Valid Tree problem.
We'll cover the following
Statement
Given an undirected graph
containing
A graph is a valid tree when all the nodes are connected and there is no cycle between them.
Constraints:
Let
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 80+ hands-on prep courses.