2 phương pháp duyệt đồ thị trong toán rời rạc năm 2024
Biểu Diễn Đồ Thị Trên Máy Tính: Toán rời rạc 2Uploaded bySo Ki Show 0% found this document useful (0 votes) 530 views 46 pages Original Titlec2 Copyright© © All Rights Reserved Available FormatsPDF, TXT or read online from Scribd Share this documentDid 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 2Uploaded bySo Ki Jump to Page You are on page 1of 46 Search inside document Reward Your CuriosityEverything 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ưở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< tham[i]=1; for (int j=1;j<=n;j++) if (tham[j]==0&&a[i][j]\==1) DFS1(j); } void DFS(){ for (int i=1;i<=n;i++) tham[i]=0; for (i=1;i<=n;i++) if (tham[i]==0) DFS1(i); } * Nhận xét - Mỗi đỉnh sẽ được thăm đúng một lần. - Thứ tự thăm phụ thuộc vào đỉnh xuất phát và phụ thuộc vào việc chọn đỉnh kề để thăm. Để kết quả thăm là duy nhất ta qui ước việc chọn đỉnh kề để thăm là theo thứ tự từ đỉnh có chỉ số nhỏ đến đỉnh có chỉ số lớn. - DFS1(v) thăm tất cả các đỉnh thuộc cùng một thành phần liên thông chứa đỉnh v. Số lần DFS gọi DFS1 chính là số thành phần liên thông của đồ thị. * Ví dụ Nếu bắt đầu từ đỉnh 4, thì thứ tự thăm có thể là: 4,1,2,3,5. CuuDuongThanCong.com https://fb.com/tailieudientucntt cuu duong than cong . com |