Duyệt cây trong đồ thị dùng thuật toán DFS và BFS

Chào mừng các bạn đến với blog it nlu,hôm nay chúng ta sẽ qua chương mới của phần bài tập về lý thuyết đồ thị.Đó là chương nói về những thuộc toán có đồ thị là một cây.Ví dụ như duyệt cây,tìm cây bao trùm có trọng số nhỏ nhất (kruskal,prim),tìm đường đi ngắn nhất (dijsktra,...),...

Ở bài đầu tiên hôm nay mình sẽ đi vào làm một bài tập cơ bản nhất đó là duyệt cây.Trong bài này mình sẽ giới thiệu cho các bạn 2 cách duyệt cây là duyệt theo chiều sâu DFS và duyệt theo chiều rộng BFS.Ở đồ thị bình thường mình cũng đã hướng dẫn các bạn làm 2 phương thức duyệt đồ thị này khá rõ.Và nó ứng dụng cho bài này khá nhiều nên nếu bạn nào chưa rõ thì dành ít phút để review lại nhé,Phong để link bên dưới nè:

Duyệt đồ thị theo chiều sâu
Duyệt đồ thị theo chiều rộng

Vì lý thuyết bài này cũng không mới mẽ gì mấy nên mình không nhắc lại nè,nó khá là giống với DFS và BFS ở đồ thị bình thường.Mình sẽ show code và giải thích lại một số chổ khác cho các bạn xem nhé!.Còn những chổ giống thì các bạn chịu khó quay lại review ở 2 bài nêu trên các bạn nha!hihi.Mình lười đó mà.

Dưới đây là code của bài tập này,các bạn xem tham khảo nhé!

Ở phần directedGraph các bạn làm tương tự nhé,chúc các bạn hoàn thành tốt bài tập này nhé!

Giấy phép Creative Commons Giấy phép Creative Commons Attribution-ShareAlike 4.0 Quốc tế .

Tạo tài khoản



Đăng nhập


Quên mật khẩu

Hoặc là :