Nút trung tâm trên cây (trong khoảng cách tối thiểu khoảng cách có nghĩa)

Question

Vấn đề của tôi là như sau:

Cho một cây (V, E), tìm nút trung tâm v sao cho tổng {w trong V} [ dist (v, w)] là tối thiểu, trong đó dist (v, w) là số cạnh trong đường đi ngắn nhất từ ​​v đến w. Thuật toán sẽ chạy trong thời gian O (n) (n là số lượng các nút trong một cây).

Các câu hỏi here và here cũng yêu cầu nút trung tâm nhưng xác định nó theo cách khác.

Tôi chưa thực hiện hết các bước nhưng tôi thực sự nghĩ rằng giải pháp cho vấn đề của tôi phải tương tự như giải pháp của this problem.

Tuy nhiên, tôi quyết định rằng tôi nên chia sẻ vấn đề của mình với cộng đồng vì tôi mất một thời gian để điều hướng đến the link, tuy nhiên không trực tiếp trả lời câu hỏi.

Answer 1

Tôi đã đưa ra giải pháp này:

1) Chọn nút tùy ý làm gốc r, tạo thành một cây. Đối với mỗi cây con trong cây này, tính toán số lượng các nút trong một cây con (các lá là một nút-cây).

Như một ví dụ cho cây

  1 
     /| \ 
     2 3 4 
    /\  \ 
    5 6  7 
     /\ 
     8 9  

này kết quả sẽ là

  9 
     /| \ 
     5 1 2 
    /\  \ 
    1 3  1 
     /\ 
     1 1  

2) Tính tổng của khoảng cách cho rễ lựa chọn này. Ví dụ: nếu bạn chọn đỉnh 1 làm gốc, tổng khoảng cách là 0 + 1 + 1 + 1 + 2 + 2 + 2 + 3 + 3 = 15

3) Di chuyển cây theo số depth-first-search cách thức. Ví dụ, bắt đầu từ đỉnh 1, chúng ta đi qua đỉnh 4. Chúng ta quan sát thấy rằng đối với 7 nút (1,2,3,5,6,8,9), chúng ta đang nhận được thêm 1 (thêm 7 = 9-2 để điểm số), cho 2 (4,7) khác, chúng ta đang tiến gần hơn 1 (trừ 2). Điều này cho phép tổng số khoảng cách bằng 15+ (9-2) -2 = 20.

Giả sử chúng ta đi qua từ 4 đến 7 tiếp theo. Bây giờ chúng ta nhận được tổng khoảng cách bằng 20+ (9-1) -1 = 27 (nhận thêm từ 8 đỉnh, và tiến gần tới 1 đỉnh).

Ví dụ khác nếu chúng ta duyệt qua từ 1 đến 2, chúng tôi nhận được tổng khoảng cách bằng 15+ (9-5) -5 = 14. Vertex 2 thực sự là giải pháp cho ví dụ này.

Đây sẽ là thuật toán của tôi.

Answer 2

Mỗi cạnh e = {a, b} có các thuộc tính sau:

• a_count = số nút để một bên (bao gồm a)
• b_count = số nút để b bên (bao gồm b)
• a_sum = tổng khoảng cách từ điểm a đến nút cây con của nó
• b_sum = tổng khoảng cách từ b đến các hạch cây con của nó

a_count cho nút e = {a, b} có thể được đánh giá như sau: * nhận tất cả các cạnh của a, không bao gồm e, tổng a_count của chúng * thêm 1 vào tổng số

a_sum for node e = {a, b} có thể được đánh giá như sau: * nhận tất cả các cạnh của a, không bao gồm e, tổng a_sum của chúng * thêm a_count (nó bao gồm +1 cho mỗi cạnh được liệt kê và +1 cho a)

Bạn có thể tự do tính toán chức năng đệ quy chấp nhận các tham số nút và hướng, lưu các kết quả thu được trong mảng toàn cầu.

Nếu bạn chạy chức năng này trên mọi cạnh của cây theo cả hai hướng, bạn sẽ có được tính toán đầy đủ cho các cạnh. Tổng thời gian cho tất cả các phép tính là O (n), vì một khi bạn nhận được một số subtree, đệ quy tự nhiên sẽ đóng toàn bộ cây con theo hướng này và các cuộc gọi tiếp theo sẽ có được kết quả từ mảng toàn cầu, và bạn chỉ thực hiện 2 * n cuộc gọi cho chức năng của bạn .

Đối với nút Một biện pháp cuối cùng là tổng của tất cả B_count + B_sum của tất cả các cạnh được kết nối với nút. Thực hiện một lần chạy đánh giá này trên các nút và chọn nút có giá trị tối thiểu.