Comment on page

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:
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()
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]]