Thắc mắc về việc tìm chu trình trong đồ thị

[mr_invincible]

Đề bài
Cho đồ thị vô hướng G = (V,E)
Tìm tất cả các chu trình từ đỉnh v cho trước
Em rất thắc mắc về đề bài trên ở chỗ chu trình là đường đi có đỉnh đầu và đỉnh cuối trùng nhau (hình như các đỉnh và cạnh có thể lặp lại). Như vậy khi dùng thuật toán tìm kiếm theo chiều sâu và rộng (DFS và BFS) thì làm thế nào để biết là đã tìm tất cả mọi trường hợp?

[bete]

Thân gửi mr_invinclible,


khi dùng thuật toán tìm kiếm theo chiều sâu và rộng (DFS và BFS) thì làm thế nào để biết là đã tìm tất cả mọi trường hợp?

=> nếu DFS thì tui sẽ xài stack; nếu BFS thì tui sẽ xài queue. Khi nào stack/queue rỗng (dĩ nhiên là không tính lúc vừa khởi tạo) thì biết là đã xét mọi trường hợp

(hiểu biết nông cạn; có gì sai sót mong được góp ý; xin cám ơn)

-thân

[mr_invincible]

Cảm ơn anh nhiều. Có vậy mà em cũng không nghĩ ra

[mr_invincible]

À em hỏi luôn. Trong 1 chu trình của đồ thị, các đỉnh và cạnh có được lặp lại không?

[mr_invincible]

Ơ mà nếu các cạnh được lặp lại => Làm sao mà tìm mọi chu trình được nhỉ? (Giả sử đỉnh A và B có đường đi => Vì các cạnh được lặp lại nên chương trình tìm chu trình sẽ đến A rồi lại đến B rồi lại đến A => Không thể hết được)
Anh Bete có thể giải thích kĩ hơn cho em chỗ này không?

[mr_invincible]

À thôi không cần nữa, em hiểu rồi. Dù sao cũng cảm ơn anh Bete