Longest path in an undirected graph

For an unweighted tree, use two traversals. Start BFS or DFS from any node, find a farthest node A, then traverse from A and take the greatest distance to a node B. The distance A to B is the tree diameter, the longest simple path. Intuitively, a farthest node from an arbitrary start is an endpoint of some diameter; in a tree there is exactly one simple path between nodes, which makes this property reliable. Record parents during the second traversal if the actual path, not only length, is required. If edges are weighted but weights are nonnegative, two DFS traversals accumulating weight work; if the input can contain cycles, this shortcut is not a general longest-path algorithm and the problem changes substantially. Handle one node (diameter zero), two nodes, star trees, and skewed chains. Each traversal visits every vertex and edge once, so time is O(n) and space O(n).