Kiểm tra graph có cycle hay k

[ngocdaothanh]

Đây là bài cty Amazon hay hỏi, chắc là vì ngắn và căn bản:

Giả sử cần viết một build tool để build các thư viện. Vì thư viện này phụ thuộc thư viện kia, nên cần build theo thứ tự. Có vấn đề là cái dependency graph này có thể có cycle.

Câu hỏi:

• Hãy viết ctrinh để ktra xem có cycle hay k.
• Nếu có cycle thì nên giải quyết thế nào để có thể build được các thư viện?

[hadv]

Hãy viết ctrinh để ktra xem có cycle hay k.

Anh thấy trong lý thuyết đồ thị có cái gọi là chu trình Hamilton. Bây giờ mình có thể áp dụng lý thuyết này vào để kiểm tra xem cái dependency graph có tồn tại cycle hay không? Nếu cái dependency graph có chu trình Hamilton thì có nghĩa là sẽ tồn tại cycle.

Nếu có cycle thì nên giải quyết thế nào để có thể build được các thư viện?

A nghĩ nếu để nguyên thì khả năng là không có cách nào để có thể build được các thư viện. Tuy nhiên, nếu gộp 2 cái thư viện tạo thành cycle thành 1 thư viện duy nhất thì có thể build đc.

Ngọc xem hướng làm của anh như vậy có ok không nhé!

[ngocdaothanh]

chu trình Hamilton...

Anh triển khai thêm là anh sẽ dùng ý tưởng về chu trình Hamilton như thế nào? Cái discussion của anh chưa chạm đến mức cho thấy là sẽ giải bài này như thế nào.

A nghĩ nếu để nguyên thì khả năng là không có cách nào để có thể build được các thư viện...

Về câu hỏi này, thì hướng là kiểu gì cũng phải loại bỏ cycle như anh nói. Còn cách loại bỏ thì có thể có nhiều cách. Gộp lại cũng là một cách. Anh thử cố đưa ra một vài cách nữa xem sao.

[hadv]

Hi Ngọc,

A triển khai ý tưởng cụ thể như bên dưới, Ngọc xem giúp anh nhé!.

Cái discussion của anh chưa chạm đến mức cho thấy là sẽ giải bài này như thế nào.

A nghĩ là sẽ sử dụng kiểu DFS để duyệt cái dependency graph như sau

1. Với mỗi thư viện gốc, thực hiện duyệt theo các nhánh mà thư viện đó phụ thuộc theo DFS
2. Đối với mỗi nhánh thực hiện duyệt qua các node (thư viện);
   • Khi duyệt qua một node (thư viện nào đó khi lưu thư viện đó vào một list
   • Kiểm tra xem nếu list đó đã tồn tại thư viện đang duyệt qua hay không? Nếu tồn tại rồi thì dừng và kết luận graph có tồn tại cycle

Anh thử cố đưa ra một vài cách nữa xem sao.

Theo anh tìm hiểu và suy nghĩ thêm thì có thể sử dụng các design pattern để tránh việc cycle dependencies. Một trong những design pattern đó là sử dụng dependency injection. Khi đó lúc build thì việc implement chỉ depend đến các abstract, còn khi run chương trình thì mới cần đến các implementation cụ thể.

[ngocdaothanh]

A nghĩ là sẽ sử dụng kiểu DFS...

OK anh thử code xem.

dependency injection...

OK.