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

Post a Comment

Popular posts from this blog

What is the AGGRCOW Problem?

Image
Aggressive cow problem is a tough nut to crack in programming as well as your real life!! This is one of the most advanced problems related to the application of binary search. The aggressive cow question is therefore generally every interviewer’s favorite. This is because to solve this problem, you need to know the basic application and concept of binary search. But how do you actually resolve the  aggressive cows problem ? Well, the answer is obvious: Using Binary Search!! Still not sure how to find the solution? Stick to this post to learn.  Here is everything you need to know about the  aggressive cows  problem and its solution.    The Problem Statement Before understanding the solution to the problem, let’s first understand the problem statement. The problem statement goes like this: John, the farmer, has constructed a new barn consisting of N stalls. He has built all these stalls in a single line X. In his barn, he has a C number of cows. His cow...
Read more

How to use Python code online?

Image
Python is a much-appreciated general-purpose programming language. It is utilized in various industries, including web development, machine learning, and desktop applications.  Luckily, the language Python has an easy-to-use syntax suitable for beginners. This makes Python an excellent language for novices to learn.  In this blog article, all of Python's fundamental concepts will be covered. You will feel confident using a  Python online compiler  to create projects. Let’s get started! About Python Python is one of the most used programming languages in modern-day, created by Guido van Rossum and released to the public in 1991. The public has free access to the source code for Python using a Python online compiler, and there are no restrictions on how it may be used or distributed, including for profit.  Practically anything may be produced with it for web development, including online web apps, mobile applications, tools, machine learning, data analytics, and m...
Read more

Fibonacci Sequence: Definition, How it Works, and How to Use It

Image
  For centuries, mathematicians were fascinated by the sequence known as Fibonacci, a fascinating mathematical notion. It is an order of values, where each value is the product of the first two numbers. The order of numbers starts at 0 or 1 and then continues endlessly. In this article, we are going to look at the sequence known as the Fibonacci series in c, how it operates, and the best way to apply it in everyday situations. What is The Fibonacci series? The sequence known as Fibonacci is a series of integers in which each one is the product of two integers before it. The order in which it starts is 0 and 1, then each successive number is product of both of the numbers following it. As a consequence, the order of numbers will be represented as follows: 0, 1, 1, 2, 3 The Fibonacci series was given the name following Leonardo Fibonacci, who popularised it in the Western world with the publication of "Liber Abaci" in 1202. However, the series became recognised in India Arabia ...
Read more