Graph Valid Tree


Introduction

The objective is to write a function that returns true (or 1) if a given undirected graph is a tree and false (or 0) if it is not a tree. A graph can be classified as a tree if it satisfies the following two conditions: -

  • Each node, except the root node, must have a single parent. That is, each node must be reached only from its parent when the tree is being traversed starting from the root.
  • We must be able to visit all the nodes of the tree starting from the root. Therefore, a tree should always be connected, and all nodes must be reachable.

 

Problem Statement

Let us consider two graphs as shown in the figure below:

 



Figure 1 shows a valid tree as it has no cycles, and has n-1 edges for n nodes.

Figure 2 is invalid as it contains a cycle connecting 1 and 2.

A function is to be written that returns 1 if the given graph is a valid tree and 0 if it is not a valid tree.

(Check out the details for the problem of the graph valid tree)

 

PsuedoCode with Explanation

Suppose there are n nodes labelled 0 to n-1 and a list of undirected edges [u,v] showing a connecting path from u to v. We have to make a function to check whether the tree formed by the given edges is valid or not.

For example, if the input is n = 5, and edge = [[0,1], [0,2], [0,3], [3,4]], as show in figure 1, then the output will be true.

 

The following steps are taken to solve this: -

  • Define a function is_valid(), this will take node, par, graph, and another array called visited.
  • If visited[node] == 1, then return true


Comments

Popular posts from this blog

Mock Test For Various Companies

What is the process of TCS's next step?

How Mock Tests Will Help You To Ace The Entrance Examinations?