Độ phức tạp về thời gian của thuật toán của Fleury

Question

Bạn có thể giúp tôi tìm ra độ phức tạp của thuật toán Fleury '(được sử dụng để lấy mạch Eulerian) không?

Answer 1

Ở đây: http://roticv.rantx.com/book/Eulerianpathandcircuit.pdf bạn có thể đọc trong số những thứ khác, rằng đó là O (E), số cạnh tuyến tính.

Answer 2

Thuật toán của Fleury không thực sự hoàn thành cho đến khi bạn xác định cách xác định các mép cầu. Tarjan đã đưa ra một thuật toán thời gian tuyến tính để xác định tất cả các cầu (xem http://en.wikipedia.org/wiki/Bridge_(graph_theory)), do đó, một triển khai ngây thơ chạy lại thuật toán của Tarjan sau mỗi cạnh đã xóa sẽ là O (E^2). Có lẽ có nhiều cách tốt hơn để tính toán lại tập các cây cầu, nhưng cũng có một thuật toán O (E) tốt hơn. (Xem http://www.algorithmist.com/index.php/Euler_tour#Fleury.27s_algorithm; không trang web của tôi :))

Answer 3

thuật toán Fleury bao gồm các bước sau:

1. Hãy chắc chắn rằng đồ thị có 0 hoặc 2 đỉnh lẻ.

2. Nếu có 0 đỉnh lẻ, hãy bắt đầu từ bất kỳ đâu. Nếu có 2 đỉnh lẻ, hãy bắt đầu từ một trong số chúng.

3. Làm theo từng cạnh một. Nếu bạn có một sự lựa chọn giữa một cây cầu và phi cầu, luôn luôn chọn phi cầu.

4. Dừng khi bạn hết các cạnh.

Nếu cầu được phát hiện ra bởi thuật toán Tarjan và những cây cầu được lưu trữ trong một ma trận kề thì chúng ta không cần phải chạy thuật toán Tarjan của mỗi thời gian để kiểm tra xem một cạnh là một cây cầu hay không. Chúng ta có thể kiểm tra nó trong O (1) thời gian cho tất cả các truy vấn cầu khác. Do đó, độ phức tạp của thuật toán Flury có thể được giảm xuống O (V + E) {vì đây là DFS} nhưng phương pháp này cần thêm không gian O (V2) để lưu trữ cầu.