5 image fixed (inlining HTTP images doesn't work anymore); for more info, see https://gist.github.com/Glorfindel83/9d954d34385d2ac2597bbe864466259f edit approved Jan 5 at 18:14 Glorfindel 26411 gold badge44 silver badges1111 bronze badges This link provides an algorithm for finding the diameter of an undirected tree using BFS/DFS. Summarizing: Run BFS on any node s in the graph, remembering the node u discovered last. Run BFS from u remembering the node v discovered last. d(u,v) is the diameter of the tree. Why does it work ? Page 2 of this provides a reasoning, but it is confusing. I am quoting the initial portion of the proof: Run BFS on any node s in the graph, remembering the node u discovered last. Run BFS from u remembering the node v discovered last. d(u,v) is the diameter of the tree. Correctness: Let a and b be any two nodes such that d(a,b) is the diameter of the tree. There is a unique path from a to b. Let t be the first node on that path discovered by BFS. If the paths $$p_1$$ from s to u and $$p_2$$ from a to b do not share edges, then the path from t to u includes s. So $$d(t,u) \ge d(s,u)$$ $$d(t,u) \ge d(s,a)$$ ....(more inequalities follow ..) http://i61.tinypic.com/rji9uq.png The inequalities do not make sense to me. This link provides an algorithm for finding the diameter of an undirected tree using BFS/DFS. Summarizing: Run BFS on any node s in the graph, remembering the node u discovered last. Run BFS from u remembering the node v discovered last. d(u,v) is the diameter of the tree. Why does it work ? Page 2 of this provides a reasoning, but it is confusing. I am quoting the initial portion of the proof: Run BFS on any node s in the graph, remembering the node u discovered last. Run BFS from u remembering the node v discovered last. d(u,v) is the diameter of the tree. Correctness: Let a and b be any two nodes such that d(a,b) is the diameter of the tree. There is a unique path from a to b. Let t be the first node on that path discovered by BFS. If the paths $$p_1$$ from s to u and $$p_2$$ from a to b do not share edges, then the path from t to u includes s. So $$d(t,u) \ge d(s,u)$$ $$d(t,u) \ge d(s,a)$$ ....(more inequalities follow ..) The inequalities do not make sense to me. This link provides an algorithm for finding the diameter of an undirected tree using BFS/DFS. Summarizing: Run BFS on any node s in the graph, remembering the node u discovered last. Run BFS from u remembering the node v discovered last. d(u,v) is the diameter of the tree. Why does it work ? Page 2 of this provides a reasoning, but it is confusing. I am quoting the initial portion of the proof: Run BFS on any node s in the graph, remembering the node u discovered last. Run BFS from u remembering the node v discovered last. d(u,v) is the diameter of the tree. Correctness: Let a and b be any two nodes such that d(a,b) is the diameter of the tree. There is a unique path from a to b. Let t be the first node on that path discovered by BFS. If the paths $$p_1$$ from s to u and $$p_2$$ from a to b do not share edges, then the path from t to u includes s. So $$d(t,u) \ge d(s,u)$$ $$d(t,u) \ge d(s,a)$$ ....(more inequalities follow ..) The inequalities do not make sense to me. 4 replaced http://cs.stackexchange.com/ with https://cs.stackexchange.com/ edited Apr 13 '17 at 12:48 ThisThis link provides an algorithm for finding the diameter of an undirected tree using BFS/DFS. Summarizing: Run BFS on any node s in the graph, remembering the node u discovered last. Run BFS from u remembering the node v discovered last. d(u,v) is the diameter of the tree. Why does it work ? Page 2 of this provides a reasoning, but it is confusing. I am quoting the initial portion of the proof: Run BFS on any node s in the graph, remembering the node u discovered last. Run BFS from u remembering the node v discovered last. d(u,v) is the diameter of the tree. Correctness: Let a and b be any two nodes such that d(a,b) is the diameter of the tree. There is a unique path from a to b. Let t be the first node on that path discovered by BFS. If the paths $$p_1$$ from s to u and $$p_2$$ from a to b do not share edges, then the path from t to u includes s. So $$d(t,u) \ge d(s,u)$$ $$d(t,u) \ge d(s,a)$$ ....(more inequalities follow ..) The inequalities do not make sense to me. This link provides an algorithm for finding the diameter of an undirected tree using BFS/DFS. Summarizing: Run BFS on any node s in the graph, remembering the node u discovered last. Run BFS from u remembering the node v discovered last. d(u,v) is the diameter of the tree. Why does it work ? Page 2 of this provides a reasoning, but it is confusing. I am quoting the initial portion of the proof: Run BFS on any node s in the graph, remembering the node u discovered last. Run BFS from u remembering the node v discovered last. d(u,v) is the diameter of the tree. Correctness: Let a and b be any two nodes such that d(a,b) is the diameter of the tree. There is a unique path from a to b. Let t be the first node on that path discovered by BFS. If the paths $$p_1$$ from s to u and $$p_2$$ from a to b do not share edges, then the path from t to u includes s. So $$d(t,u) \ge d(s,u)$$ $$d(t,u) \ge d(s,a)$$ ....(more inequalities follow ..) The inequalities do not make sense to me. This link provides an algorithm for finding the diameter of an undirected tree using BFS/DFS. Summarizing: Run BFS on any node s in the graph, remembering the node u discovered last. Run BFS from u remembering the node v discovered last. d(u,v) is the diameter of the tree. Why does it work ? Page 2 of this provides a reasoning, but it is confusing. I am quoting the initial portion of the proof: Run BFS on any node s in the graph, remembering the node u discovered last. Run BFS from u remembering the node v discovered last. d(u,v) is the diameter of the tree. Correctness: Let a and b be any two nodes such that d(a,b) is the diameter of the tree. There is a unique path from a to b. Let t be the first node on that path discovered by BFS. If the paths $$p_1$$ from s to u and $$p_2$$ from a to b do not share edges, then the path from t to u includes s. So $$d(t,u) \ge d(s,u)$$ $$d(t,u) \ge d(s,a)$$ ....(more inequalities follow ..) The inequalities do not make sense to me. 3 edited tags | link edited Jan 19 '16 at 10:44 Raphael♦ 59k2525 gold badges144144 silver badges327327 bronze badges Tweeted twitter.com/#!/StackCompSci/status/446647179676241921 occurred Mar 20 '14 at 13:59 2 edited tags | link edited Mar 20 '14 at 13:30 Raphael♦ 59k2525 gold badges144144 silver badges327327 bronze badges 1 asked Mar 20 '14 at 7:09 curryage 23622 gold badges44 silver badges88 bronze badges