Tôi có một vấn đề hw yêu cầu một thuật toán phát hiện nếu có bất kỳ chu kỳ nào trong bất kỳ đồ thị vô hướng nào có chứa bất kỳ cạnh nào 'E'. Thuật toán sẽ chạy trong thời gian tuyến tính O (N).Làm cách nào để kiểm tra xem cạnh có trong chu kỳ không?
Vấn đề tôi gặp phải là tôi không biết bắt đầu từ đâu. Tôi có một số đồ thị mẫu đơn giản nhưng tôi không biết đi đâu từ đó.
Bất kỳ gợi ý nào?
Bạn bắt đầu với cạnh 'e'. Từ đó bạn sẽ nhận được hai đỉnh nó kết nối. Từ đó bạn có các cạnh khác và các đỉnh khác, và các cạnh khác và các đỉnh khác, và ... Bạn sẽ cần một cách để tìm ra nếu một đỉnh đã được 'truy cập' bởi thuật toán của bạn. Nếu nó có thì có một chu kỳ 'e' là một phần của.
Thực hiện tìm kiếm đầu tiên chiều sâu thêm nút vào danh sách khi bạn di chuyển và xóa chúng khỏi danh sách khi bạn quay lại.
Danh sách thể hiện đường đi hiện tại của bạn.
Nếu bạn gặp một nút đã có trong danh sách của bạn, thì có vòng lặp/chu kỳ.
Đối với các cạnh (u, v):
1- thực hiện một tìm kiếm theo chiều sâu bắt đầu từ u, xác định xem v được tìm thấy và một lợi thế cạnh lại tồn tại dọc theo con đường để v
2-. thực hiện một tìm kiếm theo chiều sâu từ v, nếu u được tìm thấy và cạnh lại tồn tại để u, sau đó có một chu kỳ bao gồm cả u và v.
Nói cách khác,
1- thực hiện một DFS bắt đầu từ u , kiểm tra xem cạnh sau tồn tại và v chưa hoàn thành chưa.
2- thực hiện DFS bắt đầu từ v, kiểm tra xem cạnh sau tồn tại chưa và chưa hoàn thành nếu cả hai điều kiện là đúng, sau đó cạnh (u, v) thuộc về một chu kỳ.
Đưa ra cạnh đó (u, v) từ G. 1. Chạy BFS để xem liệu v vẫn có thể truy cập được từ u. 2. Nếu có, thì biểu đồ gốc có chu trình chứa e. bằng không thì không.
Một gợi ý? Chắc chắn rồi. Một số bộ (như hashsets) có O (1) tra cứu. – corsiKa