{"id":1879,"date":"2020-07-01T09:46:23","date_gmt":"2020-07-01T09:46:23","guid":{"rendered":"https:\/\/blog.prepbytes.com\/?p=1879"},"modified":"2022-03-29T00:22:41","modified_gmt":"2022-03-29T00:22:41","slug":"longest-path","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/longest-path\/","title":{"rendered":"Longest Path"},"content":{"rendered":"

\"\"<\/p>\n

Concepts Used<\/h3>\n
\n

Breadth First Search<\/p>\n<\/blockquote>\n

Difficulty Level<\/h3>\n
\n

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

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

Given an unweighted, undirected tree print the length of the longest path<\/p>\n<\/blockquote>\n

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

Solution Approach :<\/h3>\n

Introduction :<\/h4>\n
\n

Path lenght is the number of edges from one vertex (source) to another (destination). Idea is to perform bfs<\/strong> and store the distance of every vertex, print maximum among all the distances.<\/p>\n<\/blockquote>\n

Description :<\/h4>\n
\n

We are going to perform two bfs<\/strong> in order to find maximum path length. One for storing the path length from any of the vextex (source) ,lets say vertex v<\/code>. We will see how far we can go from this vertex v<\/code>. Another bfs<\/strong> to count the actual path length. This time our source vertex will be v<\/code> and we will move as far as possible, while maintaining a distance[]<\/code> array to store the distances for every vertex and finally return the maximum among all the distances.<\/p>\n<\/blockquote>\n

\"\"<\/p>\n

Algorithms :<\/h3>\n

bfs()<\/strong> :<\/h4>\n
\n
    \n
  1. create a queue and push the current vertex v<\/code> and update the distance of v<\/code> (distance[v]=0<\/code>). (v<\/code> is the source vertex), now perform following operations untill the queue is not empty:<\/li>\n
  2. each time we pop a vertex v<\/code> from queue, ( v<\/code> = queue.front() )<\/li>\n
  3. Iterate for all the adjacent vertices of v<\/code> and for every adjacent vertex a<\/code>, do following :<\/li>\n<\/ol>\n<\/blockquote>\n
      \n
    • if a<\/code> is unvisited update the distance as, distance[a]= distance[v]+1<\/code>.<\/li>\n
    • push a<\/code> into the queue.<\/li>\n<\/ul>\n
      \n
        \n
      1. Now when the queue becomes empty, iterate for all the vertices and return the maximum distance.<\/li>\n<\/ol>\n<\/blockquote>\n

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

        As we are performing two simple bfs, the time complexity<\/strong> of the this 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<\/blockquote>\n

        Solutions:<\/h3>\n

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