Longest Path in Undirected Acyclic Graph

Given an undirected acyclic Graph (also known as a forest, or a connected component of trees). Find the length of the longest path between between any two nodes.

The Idea: The brute force method would iterate every node in the graph, and find the maximum distance relative to that node. This would run in O(|V|^2) time. Lets think about this another way. We know that the length of the longest distance has to be between two nodes that are the greatest distance apart (in terms of number of edges). If we can find one just one of these nodes, then we know how to find the other node by by initiating a BFS from that node. This is because this node is on the 'edge' of either end of the graph, and so initiating a BFS (or DFS) would branch out to the further complementing side. So now the problem has deduced to finding one the these 'edge' nodes. To find this node, we can BFS from any part of the graph and find the node that carries the maximum distance from that node.

Complexity: O(|V|) time and space

import collections
import queue


def longest_path(edges):
    if not edges:
        return 0

    g = collections.defaultdict(list)
    for u, v in edges:
        g[u].append(v)
        g[v].append(u)

    def BFS(start):
        visited = set()
        maxx_dist = -1
        maxx_node = -1

        q = queue.Queue()
        q.put((start, 0))

        while not q.empty():
            node, dist = q.get()
            visited.add(node)

            if dist > maxx_dist:
                maxx_dist, maxx_node = dist, node

            for edge in g[node]:
                if edge not in visited:
                    q.put((edge, dist + 1))

        return maxx_node, maxx_dist

    max_node1, dist_max1 = BFS(edges[0][0])
    abs_max, abs_dist = BFS(max_node1)

    return abs_dist


edges = [[1,2], [2,3], [3,4], [4,6], [6,5], [4,8], [8,7], [7,10], [8, 11], [8,9], [9, 12]]
print(longest_path(edges))