Tìm tất cả các cơ sở chu trình trong biểu đồ, với tọa độ đỉnh được đặt

Question

Câu hỏi tương tự is posted here.

Tôi có biểu đồ không được chiếu với Vertex V và Cạnh E. Tôi đang tìm kiếm một thuật toán để xác định tất cả các cơ sở chu kỳ trong biểu đồ đó. Một ví dụ về một đồ thị như được hiển thị dưới đây:

Bây giờ, tất cả các tọa độ đỉnh là biết (không giống như câu hỏi trước, và trái với lời giải thích trong sơ đồ trên) , do đó có thể tìm thấy các chu kỳ nhỏ nhất bao gồm toàn bộ biểu đồ.

Trong biểu đồ này, có thể có các cạnh không tạo thành bất kỳ chu kỳ nào.

Thuật toán tốt nhất để làm điều này là gì?

Dưới đây là một ví dụ khác mà bạn có thể có một cái nhìn tại địa chỉ:

Giả sử rằng e1 là cạnh đó được chọn đầu tiên, và mũi tên cho thấy sự chỉ đạo của The Edge.

Answer 1

Tôi đã không cố gắng này và nó là khá tham lam nhưng nên làm việc:

1. Chọn một nút
2. Đến một của nó của các nước láng giềng
3. Tiếp tục đi cho đến khi bạn lấy lại cho nút bắt đầu của bạn , nhưng bạn không được phép ghé thăm một nút cũ.
4. Nếu bạn nhận được một chu kỳ lưu nó nếu nó không tồn tại hoặc một tập hợp con của các nút tạo nên một chu kỳ. Nếu nút trong chu trình là tập hợp con của các nút trong một chu kỳ khác, hãy loại bỏ chu kỳ lớn hơn (hoặc có thể tách nó thành hai?)
5. Bắt đầu lại ở mức 2 với hàng xóm mới.
6. Bắt đầu lại tại 1 bằng nút mới.

Nhận xét: Tại 3 bạn nên tất nhiên làm điều tương tự như đối với bước 2, vì vậy hãy thực hiện tất cả các đường dẫn có thể.

Có thể đó là sự khởi đầu? Như tôi đã nói, tôi chưa thử nó nên nó không được tối ưu.

CHỈNH SỬA: Phiên bản không được tài liệu và không được tối ưu hóa của một triển khai thuật toán có thể tìm thấy tại đây: https://gist.github.com/750015. Tuy nhiên, nó không giải quyết hoàn toàn giải pháp vì nó chỉ có thể nhận ra các tập con "đúng".