notTehlka's blog

Tree Diameter
By notTehlka, history, 3 years ago, In English

Can someone explain the logic given below for this problem.

Logic

Source

Thanks

  • Vote: I like it
  • +12
  • Vote: I do not like it

Comments Comments (14)
| Write comment?
»
3 years ago, # |
← Rev. 2   Vote: I like it +17 Vote: I do not like it

imagine a tree's diameter is drawn as a vertical line and other branches are connected to that line. from any node x, farthest node from x is always one of end points of diameter line. if there exists any node y, which is nether end point of diameter line and is farthest from x, then diameter line should be changed, to a line from (y to x) + (x to one of end points of diameter line which is farther from x). you can draw and check this. in conclusion, you can always find one of end point of diameter by finding farthest node from any node x. (i'm not good at english, hope it helped.)

→ Reply
»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Hope this helps

→ Reply
»
3 years ago, # |
  Vote: I like it +14 Vote: I do not like it

I highly recommend you watch this

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

This is the blog where the method has been proved, and this explains it using a diagram.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    Doing a bfs is fine. It also finds the distances from a vertex $$$u$$$ to all other vertexes $$$v$$$.

    → Reply
»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Why do you need a proof about it? Just believe in it

→ Reply
»
3 years ago, # |
  Vote: I like it +14 Vote: I do not like it

Because it feels right.

→ Reply
»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Hey, in case someone is looking for an intuitive explanation: here's a video explaining it using a pretty surprising way to look at the problem.

→ Reply