Làm thế nào tôi có thể tìm thấy đường dẫn thực tế được tìm thấy bởi BFS?

Question

Vấn đề tôi đang cố gắng giải quyết mối quan ngại về một cây của hệ thống MRT.

Mỗi nút có thể được kết nối tối đa 4 điểm, điều này đơn giản hóa mọi thứ. Đây là suy nghĩ của tôi.

struct stop { 
    int path, id; 
    stop* a; 
    stop* b; 
    stop* c; 
    stop* d; 
}; 

tôi có thể viết mã để lưu tất cả các thông tin mà tôi cần cho BFS để tìm kiếm tất cả các điểm, nhưng mối quan tâm chính của tôi là, mặc dù BFS tìm thấy điểm đúng cách, làm thế nào tôi có thể biết được đường đi của nó?

BFS sẽ tìm kiếm từng cấp, và khi một trong số đó đạt đến đích, nó sẽ nhảy ra khỏi vòng lặp chạy, và sau đó, tôi sẽ nhận được hàng đợi truy cập và hàng đợi chưa được sắp xếp, tôi phải nói với người dùng như thế nào những gì dừng lại ông cần phải truy cập khi hàng đợi truy cập được làm đầy với tất cả các nút BFS đã tìm kiếm?

Answer 1

Để làm như vậy, bạn cần lưu trữ map:V->V [từ đỉnh đến đỉnh], sẽ ánh xạ từ mỗi nút v, đỉnh u mà "đã phát hiện" v.

Bạn sẽ điền bản đồ này trong các lần lặp của BFS.

Sau đó - bạn có thể tái tạo lại con đường bằng cách đơn giản đi từ nút đích [trong bản đồ] - lên cho đến khi bạn nhận được trở lại nguồn, và nó là con đường Yor [đảo ngược, tất nhiên ...]

Lưu ý rằng bản đồ này có thể được thực hiện như một mảng, nếu bạn liệt kê các đỉnh.