finding longest path in an undirected and unweighted graph

please someone help , i just cant find a way to find THE LONGEST PATH IN AN UNDIRECTED AND UNWEIGHTED GRAPH
please , every where it is given that using bfs or dfs , but how bfs can solve this problem , can anybody explain, actually i have solved only 1 or 2 graph problems thats why iam unable to code this , can someone explain ???

What are you really looking for longest path from a specific node or overall longest path

  1. Use a weight variable to store weight of the corresponding nodes.
  2. Use bfs on any node(e.g. node no. 1) to find the node located farthest from the node(from node no. 1). You can do this by assigning 0 to the node( node no. 1) and then in every iteration assign the current nodes, one greater number than the node whose edge the current nodes are.( weight of current node = weight of parent node +1)
  3. Use a visit variable to mark the visited nodes so that you don’t visit them again.
  4. Iterate over every node to find the node with highest number.
  5. Reallocate the weight and visit array variable to 0 and again use bfs from node found in last step to find the node located farthest from this node.

Maybe you could try with DFS from each node, or with Floyd-Warshall algorithm. Depend on the input.

You can practice this (http://www.spoj.com/problems/PT07Z/) problem for a better understanding of the algorithm given by @rajeevkgprk

I don’t think this problem can be solved using BFS, but only through DFS. @rajeevkgprk

overall longest path
but the main problem is to find the distance from two nodes in a graph
I can use bfs twice to find the farthest nodes in the graph , but now how to find distance between them

yes , i have done this
i have found the farthest node in the graph (by using bfs twice) but now how to find the distance between them??

It will simply be the weight of farthest found node.
because the weight of node on which you began bfs was initialized to 0

but this is an unweighted graph

Of course it is an un-weighted graph.
Please do not misunderstand the use of array ‘weight[]’ here.
It is used to calculate the distance between nodes.
The weight of every node is one more than the weight of its previous connected node’s weight since it is an un-weighted graph, otherwise it would be weight of previous node + weight of the edge.
This way you can find the farthest located node by its weight.
I hope I am clear.

1 Like

thanks sir , can you give me your facebook id , i have to ask many more doubts!

gchandel6 instead you can send a message here or there

BFS is useful in case of a tree.

how did you use bfs twice and found the longest path, i am having the same problem

The algorithm you mention is for finding the diameter of the graph. For trees the diameter of the graph is equal to the length of the longest path, but for general graphs it is not.

The general longest path problem is NP-hard, so it is unlikely that anyone has found an algorithm to solve that problem in polynomial time.

1 Like