DUYỆT THEO CHIỀU SÂU

Tham khảo tài liệu duyệt theo chiều sâu, công nghệ thông tin, kỹ thuật lập trình phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả
Nội dung trích xuất từ tài liệu:
DUYỆT THEO CHIỀU SÂU Duy t theo chi u sâu Duy theo sâuThu t toán:- Ch n 1 nh làm i m b t u- B t u duy t t u cho n t n cùng c a nhánh- Sau ó s quay l i o n ư ng ã duy t, và duy t ti p nh ng nh k chưa ư c duy t- Quá trình s k t thúc khi quay l i nh b t u và t t c các nh ã ư c duy t.- Trong quá trình duy t, n u 1 nh s r qua nhi u hơn 1 nh, thì ta ch n nh có s ho c ch cái nh hơn Duy t theo chi u sâu Duy theo sâuBài t p: Duy t th sau, b t ut nh 2 Duy t theo chi u sâu Duy theo sâu Gi i thu t: S d ng quivoid DFS (bool mark[][max], int trace[], int nodes, int u){ for (int v=0;v Duy t theo chi u sâu Duy theo sâuNh n xét:- Duy t theo chi u sau c a thì bi u di n b ng danh sách k có ph c t p O(n+m) // n- S nh, m- S c nh- Duy t theo chi u sâu c a th bi u di n b ng ma ph c t p O(n2) tr n k có- Duy t theo chi u sâu thì nh duy t càng s m thì càng k t thúc mu n.- Dùng m t ngăn x p lưu tr các nh ang duy t c i ti n thu t toán Duy t theo chi u r ng Duy theoDuy t theo chi u r ng: Duy t có tính ch t “lanr ng” . Xét 1 nh b t u, và duy t t t c các nh kv i nóVí d : 4 D 2 6 B H1 5 A E 8 G 3 C 7 F Th t duy t: A, B, C, D, E, H, F, G Duy t theo chi u r ng Duy theoThu t toán:- Ch n 1 nh trong th bt u nh u tiên, i h t t t c các nh liên thông-T v i nó- Ti p t c xét v i nh th 2…- Quá trình k t thúc khi duy t xong t t c các nh Duy t theo chi u r ng Duy theoBài t p: Duy t th sau ây theo chi u r ng b t ut nh 4 Duy t theo chi u r ng Duy theo Gi i thu t:void BFS (queue Q, int trace[], bool mark[][max], int start, int nodes){ int u; Q.push(start); trace[start]=-1; do{ u=Q.front(); Q.pop(); for ( int v=0;v Duy t theo chi u r ng Duy theoNh n xét:- Duy t theo chi u sâu và duy t theo chi u r ng ch khác nha ch gi i thu t DFS s d ng Stack, và gi i thu t BFS s d ng Queue. Do ó ph c t p c a DFS và BFS là như nhau- Duy t theo chi u r ng thì nh ư c xét càng s m thì s s m duy t xongCÂY BAO TRÙM T I THI UCÂY THI Minimum spanning tree