Cấu trúc dữ liệu và giải thuật (phần 17) pptx
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (239.57 KB, 10 trang )
Duy
Duy
ệ
ệ
t theo chi
t theo chi
ề
ề
u sâu
u sâu
Thuậ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
Duy
ệ
ệ
t theo chi
t theo chi
ề
ề
u sâu
u sâu
Bài tập: Duyệt đồ thị sau, bắt đầu từ đỉnh 2
Duy
Duy
ệ
ệ
t theo chi
t theo chi
ề
ề
u sâu
u sâu
Giải thuật: Sử dụng đệ qui
void DFS (bool mark[][max], int trace[], int nodes, int u)
{ for (int v=0;v<nodes;v++)
{ if ((mark1[u][v] ==true) && (trace[v] ==0)
{ trace[v]=u;
DFS(mark,trace,nodes,v);
}
}
}
Duy
Duy
ệ
ệ
t theo chi
t theo chi
ề
ề
u sâu
u sâu
Nhậ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
trận kề có độ phức tạp O(n
2
)
- 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
Duy
ệ
ệ
t theo chi
t theo chi
ề
ề
u r
u r
ộ
ộ
ng
ng
Duyệt theo chiều rộng:
Duyệt có tính chất “lan
rộng” . Xét 1 đỉnh bắt đầu, và duyệt tất cả các đỉnh kề
với nó
Ví dụ:
A
B
D
H
C
E
G
F
1
2
4
6
5
8
7
3
Th
ứ
t
ự
duy
ệ
t: A, B, C, D, E, H, F, G
Duy
Duy
ệ
ệ
t theo chi
t theo chi
ề
ề
u r
u r
ộ
ộ
ng
ng
Thuật toán:
- Chọn 1 đỉnh trong đồ thị để bắt đầu
- Từ đỉnh đầu tiên, đi hết tất cả các đỉnh liên thông
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
Duy
ệ
ệ
t theo chi
t theo chi
ề
ề
u r
u r
ộ
ộ
ng
ng
Bài tập: Duyệt đồ thị sau đây theo chiều rộng bắt
đầu từ đỉnh 4
Duy
Duy
ệ
ệ
t theo chi
t theo chi
ề
ề
u r
u r
ộ
ộ
ng
ng
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<nodes;v++)
{ if ((mark[u][v]==true) && trace[v]=0;
{ Q.push(v);
trace[v]=u;
}
}
}while (!Q.empty());
}
Duy
Duy
ệ
ệ
t theo chi
t theo chi
ề
ề
u r
u r
ộ
ộ
ng
ng
Nhậ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 xong
CÂY BAO TR
CÂY BAO TR
Ù
Ù
M T
M T
Ố
Ố
I THI
I THI
Ể
Ể
U
U
Minimum spanning tree
Minimum spanning tree
