{"id":1873,"date":"2020-07-01T09:47:29","date_gmt":"2020-07-01T09:47:29","guid":{"rendered":"https:\/\/blog.prepbytes.com\/?p=1873"},"modified":"2022-03-23T23:03:55","modified_gmt":"2022-03-23T23:03:55","slug":"graph-tree","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/graph-tree\/","title":{"rendered":"Graph Tree"},"content":{"rendered":"

\"\"<\/p>\n

Concepts Used<\/h3>\n
\n

Depth First Search, Graph<\/p>\n<\/blockquote>\n

Difficulty Level<\/h3>\n
\n

Medium<\/p>\n<\/blockquote>\n

Problem Statement :<\/h3>\n
\n

Check whether the graph is a tree or not.<\/p>\n<\/blockquote>\n

<\/strong><\/u><\/a><\/p>\n

Solution Approach :<\/h3>\n

Introduction :<\/h4>\n
\n

For a graph to be tree, there should not be any loops and every vertex must be reachable from atleast one other vertex.<\/p>\n

This problem can be solved by many ways like Breadth First Search<\/strong>, Depth First Search<\/strong> or Disjoint Set<\/strong>. Below we are going to discuss two of the above mentioned methods to solve this problem.<\/p>\n<\/blockquote>\n

\"\"<\/p>\n

Method 1 :<\/h4>\n
\n

The graph must follow these properties:
\nIf there are n<\/code> vertices then there must be n-1<\/code> edges.
\nIt should be connected i.e. every vertex can be reached with atleast one other vertex.<\/p>\n

In trees, every node\/vertex is connected to atleast one other vertex. Also the total number of edges is also n-1<\/code> for n<\/code> nodes.<\/p>\n<\/blockquote>\n

Method 2 :<\/h4>\n
\n

The another way of checking our graph whether it is a tree or not that it should have following properties:
\nIt must not contain any cycle.
\nIt must be connected.<\/p>\n

As, we can see this approach is almost similar to the approach in method 1<\/code>, our goal is to make sure that our graph has no loops or in other words it has exactly n-1<\/code> edges and must be connected. By this way we can ensure our graph is a tree, otherwise not. Refer to the example below for better understanding.<\/p>\n

See C++<\/strong> implementation below.<\/p>\n<\/blockquote>\n

Algorithms :<\/h3>\n
\n

dfs()<\/strong> :<\/p>\n

    \n
  1. For each call, for some vertex v<\/code> ( dfs(v<\/code>) ), we will mark the vertex v<\/code> as visited (visited[v]= true<\/code>).<\/li>\n
  2. Iterate for all the adjacent vertices of v<\/code> and for every adjacent vertex a<\/code>, do following :
    \nif a<\/code> is not visited i.e visited[a]= false<\/code>,
    \nand if a<\/code> has value 1<\/code>.
    \nrecursively call dfs (a<\/code>)<\/strong>.<\/li>\n<\/ol>\n<\/blockquote>\n

    Complexity Analysis:<\/h3>\n
    \n

    The time complexity<\/strong> of the first method is represented in the form of O(V+E)<\/code>, where V<\/code> is the number of verices and E<\/code> is the number of edges.<\/p>\n

    The space complexity<\/strong> of the algorithm is O(V)<\/code> for visited[]<\/code> array.<\/p>\n<\/blockquote>\n

    Solutions:<\/h3>\n

    \t\t\t\t\t\t