Setoid
Senior Member
Bạn học đến phần đồ thị sẽ có phần phát hiện chu trình trong đồ thị có hướng, từ đó cuztomize chút là lưu được các chu trình thôi. Cụ thể bài này áp dụng dfs, mỗi khi duyệt 1 đỉnh thì lưu trạng thái đang đỉnh hiện tại đang active trên stack. trước khi dfs các hàng xóm của đỉnh này thì kiểm tra nếu có hàng xóm cũng đang active -> có chu trình.Chỗ này ko biết cách làm lắm, ai chỉ với
Đồ thị :
1->2
2->3
3->2
2->1
3->1
Thì làm sao để tìm đc các chu trình đơn:
1-2-1
1-2-3-1
2-3-2
via theNEXTvoz for iPhone
ví dụ duyệt đệ quy từ nút 1.
dfs(1) -> active(1) = true
- duyệt đệ quy hàng xóm của 1, tức là 2,3
-- dfs(2) -> active(2) = true
--- duyệt đệ quy hàng xómg của 2, tức là 1,3
--- dfs(1) . thấy active(1) already => lưu chu trình 1,2,1
--- dfs(3) -> active(3) = true
----- duyệt đệ quy hàng xóm của 3, tức là 2,1
----- dfs(2). thấy active(2) => lưu chu trình 2,3,2.
----- dfs(1). thấy active(1) => lưu chu trình 1,2,3,1.
.....
Ở cuối mỗi dfs, nhớ remove nút hiện tại không active. tức là đã duyệt xong.
Ở ngoài cùng gọi dfs cho tất cả các nút của graph.
Như các post ở trên mình cũng thấy nên học reactJs, js, html, css, db, làm 1,2 cái web projects để show hàng -> dễ xin việc hơn. Thuật toán các thứ học sau. Cái hay của computer science là bạn học theo kiểu top-down cũng được. không cần bottom-up như Toán. ví dụ để lập trình bạn không cần biết turing machine, lambda calculus, state machines; để làm web cũng không cần biết các thứ giao thức bên dưới. Biết thì tốt nhưng học dần dần cũng được.