Thuật toán thời gian tuyến tính để làm cho biểu đồ được kết nối mạnh mẽ

Question

Chúng tôi có biểu đồ tuần hoàn yếu.

Ngoài ra, chúng tôi có một bộ A giữ các đỉnh của G có độ bằng 0 và bộ B giữ các đỉnh có độ lệch bằng 0. (kích thước của A nhỏ hơn kích thước của B).

Trên hết, chúng tôi cũng biết rằng nếu các mục trong A và B có thứ tự cụ thể (ví dụ: A = a1, a2, ..., am và B = b1, b2, ..., bn) a DFS bắt đầu tại ai thăm bi (1≤ i ≤ m).

Có thể thiết kế một thuật toán thời gian tuyến tính giúp G được kết nối mạnh mẽ bằng cách thêm vào ít cạnh nhất có thể không?

Answer 1

Thêm arcs b _j -> một _{j + 1} cho j = 1, ..., m-1 và vòng cung b _j -> một cho j = m, ... , n.

Đồ thị kết quả được kết nối mạnh mẽ vì và của b của một kết nối mạnh mẽ bởi các vòng cung gia tăng và các đường dẫn từ một _i để b _i và, đối với mỗi nút x, có tồn tại i, j mà có tồn tại đường dẫn trong đồ thị ban đầu từ một số _i đến x và đường dẫn trong đồ thị ban đầu từ x đến b _j.

Chúng tôi không thể sử dụng vòng cung ít hơn, bởi vì một vòng cung đi phải được thêm vào mỗi b , ..., b _n.

Answer 2

Edited - Sau không tạo ra giải pháp với ít nhất liên kết:

Bạn có thể chạy http://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm trong thời gian tuyến tính. Tôi đề nghị bạn làm điều này và lưu ý rằng "không có thành phần được kết nối chặt chẽ nào sẽ được xác định trước bất kỳ người kế nhiệm nào". Do đó thành phần mạnh đầu tiên trong biểu đồ không được là người kế thừa của bất kỳ thành phần nào khác. Tôi đề nghị rằng mỗi khi bạn phát ra một thành phần kết nối mạnh mẽ mà không có người kế nhiệm, thì bạn thêm một liên kết kết nối nó với thành phần đầu tiên này. Tôi đề nghị bạn cũng nên thêm một liên kết mỗi lần bạn khởi động lại thuật toán Tarjan với một lời gọi không đệ quy tới strongconnect(), kết nối thành phần đầu tiên với đỉnh bạn đang khởi động lại.

Với các liên kết này, bạn có thể lấy từ thành phần mạnh đầu tiên đến mọi thành phần khác và từ mọi thành phần khác đến thành phần mạnh đầu tiên. - tiếc là điều này không nhất thiết phải là giải pháp với các liên kết ít nhất - xem bình luận thứ hai của Per bên dưới.