PDA

View Full Version : 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ó :D). 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ả.

vanchanh123
08-10-2009, 19:20
Thuong thi nhap vao ma tran m*n de bieu dien trong so cua bat ky dinh nao trong do thi,



Có cần là ma trận vuông không hay chỉ là m*n. Nói thêm chút , vì theo suy nghĩ mình thì nó vuông

quangtq
11-10-2009, 18:24
Vuông
_ Đối xứng nếu là đt vô hướng
_ Ngược lại nếu có hướng
..........................

contimhoada_nd
16-09-2010, 11:58
ai cho tui code thuat toan dfs, bfs zoi???tui dang rat can >>>>>>>>>