Làm cách nào để tìm hiểu thuật toán của Tarjan?

Question

Tôi đã cố gắng tìm hiểu thuật toán của Tarjan từ Wikipedia trong 3 giờ, nhưng tôi không thể làm cho đầu hoặc đuôi của nó. :(

http://en.wikipedia.org/wiki/Tarjan's_strongly_connected_components_algorithm#cite_note-1

Tại sao nó một cây con của cây DFS? (Trên thực tế DFS tạo ra một khu rừng? O_O) Và tại sao v.lowlink=v.index ngụ ý rằng v là cội rễ?

Có thể ai đó xin giải thích Điều này cho tôi/cung cấp trực giác hoặc động lực đằng sau thuật toán này?

Answer 1

Ý tưởng là: Khi đi ngang qua cây, mỗi khi bạn tìm kiếm một nhánh và quay ngược lại, bạn kiểm tra xem bạn đã gặp phải một nút 'trên' trong cây.

• Nếu bạn không (if (v.lowlink = v.index)), sau đó bạn vừa hoàn thành một SCC - nó bao gồm các nút hiện hành và tất cả các nút trên stack. Đó chính xác là một cây con của cây DFS, ngoại trừ các nút trong các SCC đã được hoàn thành.

• Nếu bạn đã làm, bạn tuyên truyền thông tin này cho các nút 'trên' (v.lowlink := min(v.lowlink, w.lowlink)), bởi vì kết hợp với đường dẫn trong cây DFS cạnh tạo ra một đường dẫn 'hướng lên'.

DFS tạo rừng nhưng bạn luôn luôn xem xét một cây một lần. Một SCC luôn luôn được bao gồm trong một cây DFS, nếu không (là một SCC) sẽ có một con đường trong cả hai hướng giữa cả hai (tất cả) cây trong câu hỏi - đó là một mâu thuẫn.

Answer 2

chỉ thêm vào câu trả lời của pjotr: v.lowlink về cơ bản là chỉ mục của nút trên cùng mà bạn đã tìm thấy trong cây. Hãy nhớ rằng tối đa trong bối cảnh này có nghĩa là tối thiểu khi bạn tiếp tục tăng chỉ số khi bạn đi xuống. Bây giờ sau khi xử lý tất cả những người kế của bạn, có cơ bản ba trường hợp:

1. v.lowlink < v.index: Điều này cho thấy bạn đã tìm được một lợi thế cạnh lại. Lưu ý rằng chúng tôi không có chỉ tìm thấy bất kỳ cạnh sau nào, nhưng một điểm trỏ đến một nút "nằm trên" nút hiện tại. Đó là điều v.lowlink < v.index ngụ ý.

2. v.lowlink = v.index: Điều chúng tôi biết trong trường hợp này là không có cạnh sau nào đề cập đến bất kỳ điều gì phía trên nút hiện tại. Có thể có một cạnh sau cho nút này (có nghĩa là một trong các nút kế thừa của bạn w có một liên kết thấp sao cho w.lowlink = v.lowlink = v.index). Nó cũng có thể là có một cạnh sau đề cập đến một cái gì đó bên dưới nút hiện tại, có nghĩa là có một thành phần được kết nối mạnh mẽ bên dưới nút hiện tại đã được in ra rồi. Tuy nhiên, nút hiện tại chắc chắn là gốc của một thành phần được kết nối mạnh mẽ.

3. v.lowlink> v.index: Điều đó thực sự không thể thực hiện được. Tôi chỉ liệt kê nó vì mục đích hoàn chỉnh. ;)

Hy vọng điều đó sẽ hữu ích!

Answer 3

Một số Trực giác về những cái Tarjan Thuật toán:

• Trong DFS, khi chúng ta gặp phải một lợi thế cạnh trở lại từ đỉnh v, chúng tôi cập nhật tổ tiên có thể truy cập thấp nhất tức là chúng tôi cập nhật giá trị của thấp [v]

• Bây giờ khi tất cả các cạnh đi của đỉnh được xử lý tức là chúng ta sắp thoát lệnh DFS cho đỉnh v, chúng ta kiểm tra giá trị của [v] thấp, dù thấp [v] == v (Giải thích dưới đây) . Nếu không có nghĩa là v không phải là gốc của SCC và bây giờ chúng tôi cung cấp lợi ích cho cha mẹ của v.đến tổ tiên có thể truy cập thấp nhất của cha mẹ [v] bây giờ đã được thay đổi thành [v] thấp.

này nghe có vẻ logic như thể mặc dù không có lợi thế cạnh lại trực tiếp từ cha mẹ [v] để tổ tiên của v, nhưng có một con đường (cạnh sau của v + cạnh đối v) qua đó phụ huynh [v] vẫn có thể tiếp cận tổ tiên của v. Vì vậy, chúng tôi cũng đã cập nhật [parent [v]] thấp ở đây. Vì vậy, chúng tôi sẽ tiếp tục cập nhật chuỗi này và [v] thấp cho tất cả v sẽ tiếp tục cập nhật cho đến khi chúng tôi tiếp cận với tổ tiên (thông qua backtracking). Đối với tổ tiên này thấp [v] sẽ bằng v. Và do đó điều này sẽ hoạt động như là gốc của SCC.

Hy vọng điều này sẽ giúp