Biểu Diễn Đồ Thị Trên Máy Tính: Toán rời rạc 2
Uploaded by
So Ki
0% found this document useful [0 votes]
530 views
46 pages
Original Title
c2
Copyright
© © All Rights Reserved
Available Formats
PDF, TXT or read online from Scribd
Share this document
Did you find this document useful?
Is this content inappropriate?
0% found this document useful [0 votes]
530 views46 pages
Biểu Diễn Đồ Thị Trên Máy Tính: Toán rời rạc 2
Uploaded by
So Ki
Jump to Page
You are on page 1of 46
Search inside document
Reward Your Curiosity
Everything you want to read.
Anytime. Anywhere. Any device.
No Commitment. Cancel anytime.
Chương 3
CÁC THUẬT TOÁN DUYỆT VÀ TÌM KIẾM TRÊN ĐỒ THỊ
- Tìm theo chiều sâu [Depth First Search]
* Ý tưởng
- Từ đỉnh v1 nào đó chưa thăm, thăm v1. Tìm đỉnh v2 chưa thăm kề với v1, thăm v2. Tìm đỉnh v3
chưa thăm kề với v2, thăm v3… Lặp lại việc thăm cho tới khi tất cả các đỉnh đều được thăm.
- Nếu tại một đỉnh vi nào đó, không còn đỉnh nào kề với vi là chưa thăm thì quay trở lại đỉnh vi-1 tìm
đỉnh kề chưa thăm nếu có của vi-1 để thăm.
* Cài đặt
const int Max=20;
int a[Max][Max],n, tham[Max];
void DFS1[int i]{
cout