Tìm hiểu độ sâu của biểu đồ từ mỗi nút

Question

Tôi gặp vấn đề khi tìm chiều sâu tối thiểu có thể có của biểu đồ ngụ ý rằng tôi phải tìm độ sâu tối đa từ mỗi nút và trả lại ít nhất tất cả. Rõ ràng là một DFS đơn giản từ mỗi nút sẽ thực hiện thủ thuật nhưng khi mọi thứ trở nên điên rồ với đầu vào cực lớn, thì DFS trở nên không hiệu quả (giới hạn thời gian). Tôi đã cố gắng giữ khoảng cách của mỗi chiếc lá đến nút đang được khám phá trong bộ nhớ nhưng điều đó không giúp được gì nhiều.

Làm cách nào để tìm hiệu quả độ sâu tối thiểu của biểu đồ rất lớn. Điều đáng lưu ý là biểu đồ được đề cập có không có chu kỳ.

Answer 1

Để tìm đồ thị trung tâm/trung tâm của một đồ thị dưới cây vô hướng bạn có thể:

1. Đừng một DFS để tìm một danh sách tất cả các nút lá O (n)
2. Hủy bỏ tất cả các nút lá từ đồ thị và lưu ý trong việc xóa mà nút mới trở thành nút lá
3. Lặp lại bước 2 cho đến khi đồ thị là hoàn toàn bị xóa

nút/nút xóa trong giai đoạn cuối cùng của thuật toán sẽ là đồ thị trung tâm của cây của bạn.

Mỗi nút bị xóa một lần, vì vậy toàn bộ quá trình này có thể được thực hiện trong O (n).

Answer 2

gì bạn dường như tìm đường kính /2. Bạn có thể tính toán đường kính của một cây như dưới đây và gọi nó là như findDiameter(n, null), cho một nút tùy ý n của cây.

public findDiameter(node n, node from) returns <depth, diameter> 

    // apply recursively on all children 
    foreach child in (neighbors(n) minus from) do 
     <de, di> = findDiameter(child, n) 

    // depth of this node is 1 more than max depth of children 
    depth = 1 + max(de) 

    // max diameter either uses this node, then it is 1 + the 2 largest depths 
    // or it does not use this node, then it's the max depth of the neighbors 
    diameter = max(max(di), 1 + max(de) + oneButLargest(de)) 

Tất cả những gì bạn cần làm là lặp lại những người hàng xóm theo dõi đường kính lớn nhất và 2 độ sâu lớn nhất.