Xác định khoảng cách giữa hai nút ngẫu nhiên trong một cây

Question

Với một cây chung, tôi muốn khoảng cách giữa hai nút v và w.

Wikipedia states the following:

Tính của tổ tiên chung thấp nhất có thể hữu ích, ví dụ, như một phần của một thủ tục để xác định khoảng cách giữa các cặp nút trong một cây: khoảng cách từ v đến w có thể được tính bằng khoảng cách từ gốc đến v, cộng với khoảng cách từ gốc đến w, trừ đi khoảng cách gấp đôi từ gốc đến tổ tiên chung thấp nhất của chúng.

Hãy nói rằng d(x) biểu thị khoảng cách của nút x từ gốc mà chúng tôi thiết lập để 1. d(x,y) biểu thị khoảng cách giữa hai đỉnh x và y. lca(x,y) biểu thị tổ tiên chung thấp nhất của cặp đỉnh x và y.

Do đó nếu chúng tôi có 4 và 8, lca(4,8) = 2 do đó, theo mô tả ở trên, d(4,8) = d(4) + d(8) - 2 * d(lca(4,8)) = 2 + 3 - 2 * 1 = 3. Tuyệt vời, điều đó đã hiệu quả!

Tuy nhiên, các trường hợp đã nêu ở trên dường như thất bại cho các cặp đỉnh (8,3) (lca(8,3) = 2) d(8,3) = d(8) + d(3) - 2 * d(2) = 3 + 1 - 2 * 1 = 2. này là không chính xác tuy nhiên, khoảng cách d(8,3) = 4 như có thể được nhìn thấy trên đồ thị. Thuật toán dường như thất bại cho bất cứ điều gì vượt qua gốc xác định.

Tôi đang thiếu gì?

Answer 1

Bạn đã bỏ lỡ số lca(8,3) = 1 và không phải = 2. Do đó, d(1) == 0 làm cho nó:

d(8,3) = d(8) + d(3) - 2 * d(1) = 3 + 1 - 2 * 0 = 4 

Answer 2

Đối với 2 nút thích hợp, cụ thể là một trong những quyền này, d(lca(8,2)) == 0, không phải 1 như bạn có nó trong nguồn gốc của mình. Khoảng cách từ gốc - đó là lca trong trường hợp này - chính nó là bằng không. Vì vậy,

d(8,2) = d(8) + d(2) - 2 * d(lca(8,2)) = 3 + 1 - 2 * 0 = 4 

Thực tế là bạn có hai nút có nhãn 2 có lẽ là điều khó hiểu.

Edit: Bài viết đã được chỉnh sửa để một nút ban đầu dán nhãn 2 hiện đang được dán nhãn 3. Trong trường hợp này, các nguồn gốc bây giờ là đúng nhưng tuyên bố

the distance d(8,2) = 4 as can be seen on the graph 

là không chính xác, d (8 , 2) = 2.