Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email
Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

# Longest Path

Last Updated on March 29, 2022 by Ria Pathak

Medium

### Problem Statement :

Given an unweighted, undirected tree print the length of the longest path

See original problem statement here

### Solution Approach :

#### Introduction :

Path lenght is the number of edges from one vertex (source) to another (destination). Idea is to perform bfs and store the distance of every vertex, print maximum among all the distances.

#### Description :

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

### Algorithms :

#### bfs() :

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

### Complexity Analysis:

As we are performing two simple bfs, the time complexity of the this method is represented in the form of `O(V+E)`, where `V` is the number of verices and `E` is the number of edges.

### Solutions:

```
#include <stdio.h>
#include <stdlib.h>
#include<string.h>
#define INT_MIN -9999

struct pair {
void *first;
void *second;
};

void FreePair(struct pair* pair) {
free(pair->first);
free(pair->second);
free(pair);
}

struct pair* MakePair(void *f, void *s, size_t fsize, size_t ssize) {
struct pair* p = malloc(sizeof(struct pair));
if (p == NULL) return NULL;
p->first = malloc(fsize);
p->second = malloc(ssize);
if (p->first == NULL || p->second == NULL) {
FreePair(p);
return NULL;
}
memcpy(p->first, f, fsize);
memcpy(p->second, s, ssize);
return p;
}

struct node {
int vertex;
struct node* next;
};
struct node* createNode(int);

struct Graph {
int numVertices;
};

// Create a node
struct node* createNode(int v) {
struct node* newNode = malloc(sizeof(struct node));
newNode->vertex = v;
newNode->next = NULL;
return newNode;
}

// Create a graph
struct Graph* createAGraph(int vertices) {
struct Graph* graph = malloc(sizeof(struct Graph));
graph->numVertices = vertices;

graph->adjLists = malloc(vertices * sizeof(struct node*));

int i;
for (i = 0; i < vertices; i++)

return graph;
}

void addEdge(struct Graph* graph, int s, int d) {
// Add edge from s to d
struct node* newNode = createNode(d);

// Add edge from d to s
newNode = createNode(s);
}

//QUEUE
struct Queue
{
int front, rear, size;
unsigned capacity;
int* array;
};

// function to create a queue of given capacity.
// It initializes size of queue as 0
struct Queue* createQueue(unsigned capacity)
{
struct Queue* queue = (struct Queue*) malloc(sizeof(struct Queue));
queue->capacity = capacity;
queue->front = queue->size = 0;
queue->rear = capacity - 1;  // This is important, see the enqueue
queue->array = (int*) malloc(queue->capacity * sizeof(int));
return queue;
}

// Queue is empty when size is 0
int isEmpty(struct Queue* queue)
{  return (queue->size == 0); }

// Function to add an item to the queue.
// It changes rear and size
void enqueue(struct Queue* queue, int item)
{

queue->rear = (queue->rear + 1)%queue->capacity;
queue->array[queue->rear] = item;
queue->size = queue->size + 1;
//printf("%d enqueued to queue\n", item);
}

// Function to remove an item from queue.
// It changes front and size
int dequeue(struct Queue* queue)
{
if (isEmpty(queue))
return INT_MIN;
int item = queue->array[queue->front];
queue->front = (queue->front + 1)%queue->capacity;
queue->size = queue->size - 1;
return item;
}

// Function to get front of queue
int front(struct Queue* queue)
{
if (isEmpty(queue))
return INT_MIN;
return queue->array[queue->front];
}

struct pair* bfs(struct Graph *graph, int u,int V)
{

int dis[V];
memset(dis, -1, sizeof(dis));

struct Queue* q = createQueue(100000);
enqueue(q,u);

dis[u] = 0;

while (!isEmpty(q))
{
int t = dequeue(q);
struct node * temp = graph->adjLists[t];

while(temp)
{

if (dis[temp->vertex] == -1)
{
enqueue(q,temp->vertex);
dis[temp->vertex] = dis[t] + 1;
}

temp = temp->next;
}
}

int maxDis = 0;
int nodeIdx;

for (int i = 0; i < V; i++)
{
if (dis[i] > maxDis)
{
maxDis = dis[i];
nodeIdx = i;
}
}
return MakePair(&nodeIdx, &maxDis,sizeof(nodeIdx),sizeof(maxDis));
}

void longestPathLength(struct Graph* graph,int n)
{
struct pair * t1,*t2;
t1 = bfs(graph,0,n);
t2 = bfs(graph,*(int *)t1->first,n);

printf("%d\n", *(int *)t2->second);
}

int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n,m,u,v;
scanf("%d %d",&n,&m);
struct Graph* graph = createAGraph(n);
while(m-->0)
{
int a,b;
scanf("%d %d",&a,&b);
}
longestPathLength(graph,n);
}
return 0;
}
```
```
#include <bits/stdc++.h>
using namespace std;

class Graph
{
int V;
public:
Graph(int V);
void longestPathLength();
pair<int, int> bfs(int u);

};

Graph::Graph(int V)
{
this->V = V;
}

{
}

pair<int, int> Graph::bfs(int u)
{

int dis[V];
memset(dis, -1, sizeof(dis));

queue<int> q;
q.push(u);

dis[u] = 0;

while (!q.empty())
{
int t = q.front();     q.pop();

{
int v = *it;

if (dis[v] == -1)
{
q.push(v);
dis[v] = dis[t] + 1;
}
}
}

int maxDis = 0;
int nodeIdx;

for (int i = 0; i < V; i++)
{
if (dis[i] > maxDis)
{
maxDis = dis[i];
nodeIdx = i;
}
}
return make_pair(nodeIdx, maxDis);
}

void Graph::longestPathLength()
{
pair<int, int> t1, t2;
t1 = bfs(0);
t2 = bfs(t1.first);

cout<< t2.second<<endl;
}

int main()
{
int t;
cin>>t;
while(t--)
{
int n,e;
cin>>n>>e;

Graph g(n);
while(e--)
{
int u,v;
cin>>u>>v;
}

g.longestPathLength();
}
return 0;
}
```
```
import java.util.*;

class Main {

static class Pair<T,V> {
T first;
V second;

Pair(T first, V second) {
this.first = first;
this.second = second;
}
}

static class Graph {
int V;

// Constructor
Graph(int V) {
this.V = V;
for(int i = 0; i < V; ++i) {
}
}

void addEdge(int s, int d) {
}

Pair<Integer, Integer> bfs(int u) {
int[] dis = new int[V];

Arrays.fill(dis, -1);

dis[u] = 0;
while (!q.isEmpty()) {
int t = q.poll();

for(int i = 0; i < adj[t].size(); ++i) {

if(dis[v] == -1) {

dis[v] = dis[t] + 1;
}
}
}

int maxDis = 0;
int nodeIdx = 0;

for(int i = 0; i < V; ++i) {
if(dis[i] > maxDis) {
maxDis = dis[i];
nodeIdx = i;
}
}

return new Pair<Integer, Integer>(nodeIdx, maxDis);
}

void longestPathLength() {
Pair<Integer, Integer> t1, t2;
t1 = bfs(0); // first bfs

// second bfs to find actual longest path
t2 = bfs(t1.first);

System.out.println(t2.second);
}
}

public static void main(String[] args){
// Create a graph given in the example
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while(t-->0)
{
int n = sc.nextInt();
int e = sc.nextInt();

Graph graph = new Graph(n);
while(e-->0)
{
int u = sc.nextInt();
int v = sc.nextInt();
}

graph.longestPathLength();
}
}

}
```

[forminator_quiz id="1941"]

This article tried to discuss Breadth First Search. Hope this blog helps you understand and solve the problem. To practice more problems on Breadth First Search you can check out MYCODE | Competitive Programming.