Cho đệ hỏi tý về mấy thuật toán tìm kiếm bfs, dfs..????

**john_vn** · 07-04-2005 22:39

Làm thế nào đệ input dữ liệu bài toán vào trong thuật toán của mình . Các giải thuật BFS, DFS đệ hiểu nhưng không biết cách vận dụng và tìm cấu trúc dữ liệu để lưu trữ.
Ví dụ một bài đơn giản, các huynh giúp nhé :
A-> B -> C - > D
A-> E -> F
B-> G
C-> G -> H -> I
D-> K
Tìm đường đi từ A đến I
(Xin lỗi đệ không vẽ lên được, các huynh theo dấu đưởng dẫn trên để suy ra cây nha)
Bây giờ đệ phải khai báo một cấu trúc như thế nào đây để biểu diễn "cái cây" theo đề bài.
Nếu có thể xin huynh cho đệ code của cấu trúc đó luôn hen (Đệ chỉ cần chỉ cho đệ cấu trúc để lưu trữ nó thôi, còn thuật toán thì đệ hiểu rùi)
Thanks alot.

**songok** · 15-04-2005 18:16

Co 3 cach de bieu dien cau truc do thi :
1. Ma tran ke
2. Danh sach canh
3. Danh sach ke

Thuong thi nhap vao ma tran m*n de bieu dien trong so cua bat ky dinh nao trong do thi, Neu do thi thua ( tuc 0 nhieu hon 1 ) ta thuong dung danh sach ke de chua

input vao la
1 2
1 3
2 4
...
tuc la 1 co the den duoc 2, 3. 2 den duoc 4... Thong thuong ta hay su dung 2 cach nay de input vao cho bai toan do thi

**ongquach** · 21-06-2007 08:26

Hic cac' dai ka noi' ro~ ho em fan` luu = danh sach' lan can. ke` kai'. Noi' tum' tum' zay. em doc. hong hieu?

Thanks!!!

**truongngocdai** · 22-06-2007 11:03

Danh sách kề là cách cài đặt tốt nhất (nếu không kể đến cái tính khó cài đặt của nó

). Chỉ dùng Danh sách kề khi dùng 2 phương pháp có quá nhiều nhược điểm.

**SupaTrupa** · 25-06-2007 00:54

Theo mình biết thì để lưu dữ liệu là
1) adjacency matrix
2) adjacency lists

Với adjacency lists thì nếu bạn có 5 nodes, thì phải có 5 lists. List 1 lưu danh sách những nodes mà node 1 có thể đi tới, list 2 lưu danh sách những nodes mà node 2 có thể đi tới.
Với adjacency matrix thì tương đối dễ hiểu.

Với 1 bài toán bật kì thì mình thích dùng adjacency matrix hơn vì kích cỡ của nó sẽ cố định và dễ hiểu hơn. Còn nếu muốn tìm hiểu về effciency (~số phép tính) của 2 thằng này thì dùng công thức efficency của adjacency matrix là Omega(V^2) còn của adjacency list là Omega(V+E) [V(vertex) là đỉnh còn E(edge) là cạnh]. Nếu bạn muốn làm chương trình nhanh hơn thì mới lo chứ không thì cứ dùng matrix.

DFS và BFS có nhiều công dụng giống nhau nhưng mỗi cái lại có nhiều công dụng riêng(tìm google: applications DFS BFS). Trong bài của bạn tốt nhất là nên dùng BFS.
Nếu muốn tìm đường giữa 2 node bất kì i và j thì BFS từ node i hoặc j. (Chú ý path mà bạn tìm được với BFS là path mà có số cạnh nhỏ nhất nhưng có thể không phải là path ngắn nhất. Nếu muốn tìm path ngắn nhất thì nên áp dụng topological sorting)

**TIG_Messi** · 09-07-2007 14:40

Với những bài toán lớn thì việc biểu diễn ma trận kề rất tốn bộ nhớ, VD với mảng 1000x1000 thì phải biểu diễn tới tối đa 10^12 đỉnh kề, chưa kể đến các con trỏ.
Với những bài lớn thì nên dùng Function kề để duyệt các đỉnh kề của từng đỉnh 1 và cho vào hàng đợi.

**SupaTrupa** · 10-07-2007 15:31

Bác TIG_messi sai rồi.

Yếu tố quyết định khi chọn giữa adjacency matrix và adjacency list không phải nằm ở độ lớn của dữ liệu mà nằm ở complexity của thuật toán trên từng thằng. Như mình đã nói ở trên complexity của DFS/BFS trên adjacenct matrix là Omega(V^2) còn adjacency list là Omega(V+E)

Trong trường hợp xấu nhất thì dùng adjacency list còn tốn dữ liệu hơn adjacency matrix nữa, đó là trường hợp khi tất cả các đỉnh đều đi tới các đỉnh khác. Dùng adjacency list thường phải khởi tạo list với initial size và dynamically expand cái array này khi đọc dữ liệu. Khi expand array, bác phải nói hệ thống allocate new memory và copy dữ liêu trong array hiện tại qua array mới. Trong nhiều trường hợp việc access vào hệ thống như vậy rất chậm (trong lan).

Ngoài ra, bác không thể nói là trung bình thì dùng adjacency list chương trình chỉ cần 56kb memory (trong khi adjacency matrix cần 90kb) nên tôi chỉ cần 60kb memory. Nếu bác gặp phải trường hợp xấu nhất khi chương trình cần 80kb thì sao? Lúc nào cũng phải tính tới worst case scenario cả.