finding longest path in an undirected and unweighted graph

general
, ,
1

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 ???

2

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

3
  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.
4

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

5

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??

6

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

7

but this is an unweighted graph

8

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
9

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

10

gchandel6 instead you can send a message here or there

11

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

12

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

13

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

14

BFS is useful in case of a tree.