Longest path in a tree | Code Marvels

Given an unweighted and undirected tree,the task is to find the length of the longest path (from one node to another) in that tree.The length of a path in this case is number of edges we traverse from source to destination.

Example-

Number of nodes=3
Number of edges=2
Edges-
1 2
2 3

Output-
2
(1->2->3 is the longest path in the given tree which has a length of 2 units).

Algorithm-

1.Loop through the vertices, starting a new depth first search whenever the loop reaches a vertex that has not already been included in previous DFS calls.
2.A dist[] array is constructed to record the distances of all the vertices from the starting vertex ie. vertex on which DFS is called.
3.Maximum of all the values of the dist[] array is found and the respective vertex number is found.Let it be v.
4.Now,DFS is called on v and dist[] array records the distances of all the vertices from the vertex v.
5.Maximum of all the values of the dist[] array is the final answer that is it is the length of the longest path in the tree.

Code-


#include<stdio.h>
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;


vector<int>arr[10005];

int n,a,b,j=0,m;

int color[10005],dist[10005];

//d denotes the distance of the node on which DFS is called from the starting vertex.
void dfs(int node,int d)
{
     color[node]=2;
//marking the visited vertices

     dist[node]=d;

     for(int i=0;i<arr[node].size();++i)
     {
                   
         if(color[arr[node][i]]==0)
           {
            dfs(arr[node][i],d+1);
           }
     }  
}

int main()
{
    int p;
    
    int i1;
    p=1;j=0;

//n is the number of vertices
    scanf("%d",&n);

    for(i=0;i<n;i++)
    arr[i].clear();
    for(i=0;i<n;++i)
{
     color[i]=0;dist[i]=0;
 }

//tree has n-1 edges

     while(j<n-1)
{
               scanf("%d %d",&a,&b);
//a and b denote the starting and ending vertices of an edge

               arr[a-1].push_back(b-1);
               arr[b-1].push_back(a-1);
               j++;
       }
               for(i=0;i<n;++i)
          {
                  if(color[i]==0)
                    dfs(i,0);
         }

     int max=0;

// p denotes the vertex with maximum distance

     for(i=0;i<n;i++)
     {
                        if(dist[i]>=max)

             {          max=dist[i];
                        p=i;
              }
     }
//resetting the arrays to call DFS again

                    for(i=0;i<n;++i)
          {
                       color[i]=0;dist[i]=0;
          }

//calling dfs on vertex which has max distance

dfs(p,0);  
max=0;
for(i=0;i<n;i++)
     {
                        if(dist[i]>=max)

             {          max=dist[i];
                        p=i;
              }
     }         
                 
cout<<max<<endl;
                
return 0;

}

Leave a Reply Cancel reply