zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Khoa Học Tự Nhiên

Bài giảng lý thuyết đồ thị - Chương 3

Chia sẻ: Nguyễn Nhi | Ngày: | Loại File: PDF | Số trang:20

Báo xấu

118
lượt xem 21
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

CÁC THUẬT TOÁN TÌM KIẾM TRÊN ĐỒ THị VÀ ỨNG DỤNG Trong lý thuyết đồ thị, có rất nhiều thuật toán được xây dựng dựa trên cơ sở duyệt qua tất cả các đỉnh của đồ thị sao cho mỗi đỉnh chỉ được duyệt đúng một lần. Do vậy, việc xây dựng các thuật toán cho phép duyệt qua tất cả các đỉnh của đồ thị một cách có hệ thống là một vấn đề quan trọng thu hút sự quan tâm nghiên cứu của nhiều nhà khoa học. ...

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng lý thuyết đồ thị - Chương 3

Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ Chương 3 CÁC THUẬT TOÁN TÌM KIẾM TRÊN ĐỒ THN VÀ ỨNG DỤNG Trong lý thuyết đồ thị, có rất nhiều thuật toán được xây dựng dựa trên cơ sở duyệt qua tất cả các đỉnh của đồ thị sao cho mỗi đỉnh chỉ được duyệt đúng một lần. Do vậy, việc xây dựng các thuật toán cho phép duyệt qua tất cả các đỉnh của đồ thị một cách có hệ thống là một vấn đề quan trọng thu hút sự quan tâm nghiên cứu của nhiều nhà khoa học. Các thuật toán như vậy được gọi chung là thuật toán tìm kiếm trên đồ thị. Trong chương này chúng ta sẽ nghiên cứu hai thuật toán tìm kiếm cơ bản trên đồ thị là Thuật toán tìm kiếm theo chiều sâu (Depth First Search) và Thuật toán tìm kiếm theo chiều rộng (Breadth First Search) và một vài ứng dụng của hai thuật toán này. Để đơn giản cho việc trình bày, chúng ta sẽ xét đồ thị vô hướng G = (V,E), |V| = n, |E| = m; Đồ thị có hướng sẽ được suy ra một cách tương tự với một vài điểm đặc biệt cần chú ý. Để đánh giá hiệu quả của các thuật toán này, chúng ta chỉ chú trọng đến việc đánh giá độ phức tạp tính toán của thuật toán, tức số phép toán mà thuật toán cần thực hiện trên mọi bộ dữ liệu vào trong trường hợp xấu nhất. Độ phức tạp tính toán này được biểu diễn bằng một hàm số của kích thước dữ liệu đầu vào. Cụ thể ở đây kích thước của dữ liệu vào sẽ là số đỉnh n và số cạnh m của đồ thị. Khi đó độ phức tạp tính toán của thuật toán sẽ được biểu diễn bằng hàm hai biến f(n,m) là số phép toán nhiều nhất mà thuật toán cần phải thực hiện đối với mọi đồ thị n đỉnh, m cạnh. Để so sánh tốc độ tăng của hai hàm nhận giá trị không âm f(n) và g(n) chúng ta sử dụng ký hiệu f(n) = O(g(n)). Điều này có nghĩa tương đương với việc tìm được các hằng số dương C và N sao f (n) ≤ Cg (n); ∀n ≥ N cho: Trường hợp mở rộng, nếu f(n1,n2,..,nk) và g(n1,n2,..,nk) là các hàm biểu diễn, ta viết: f(n1,n2,..,nk)=O(g(n1,n2,..,nk)) ⇔ Tìm được các hằng số dương C và N sao cho: f(n1,n2,..,nk) ≤ Cg(n1,n2,..,nk) với ∀n ≥ N Nếu độ phức tạp tính toán của thuật toán là O(g(n)) thì ta nói là thuật toán có thời gian tính toán cỡ O(g(n)). 3.1 Thuật toán tìm kiếm theo chiều sâu trên đồ thị (Depth First Search) Ý tưởng chính của thuật toán tìm kiếm theo chiều sâu có thể được hiểu như sau: Ban đầu tất cả các đỉnh của đồ thị đều chưa được duyệt đến, ta sẽ bắt đầu việc tìm kiếm từ một đỉnh nào đó, giả sử đỉnh đó là v1. Sau đó chọn u là một đỉnh (có thể chọn tuỳ ý) trong danh sách các đỉnh kề với đỉnh v1 mà chưa được xét đến và lặp lại quá trình tìm kiếm đối với đỉnh u này. Ở bước tổng quát, giả sử đang xét đỉnh vk, nếu trong các đỉnh kề với đỉnh vk ta tìm được đỉnh w là đỉnh chưa được duyệt đến thì ta sẽ lại bắt đầu quá trình tìm kiếm từ đó và w sẽ trở thành đỉnh đã được duyệt qua. Nếu không còn đỉnh nào kề với đỉnh vk là chưa được duyệt đến thì ta nói rằng đỉnh này đã được duyệt xong và quay lại tiếp tục tìm kiếm từ đỉnh mà trước đó ta đến được đỉnh vk. Quá trình cứ tiếp tục như vậy cho đến khi tất cả các đỉnh của đồ thị đã được duyệt hết. Như vậy ta có thể hiểu một cách đơn giản là việc tìm kiếm theo chiều sâu trên đồ thị bắt đầu từ đỉnh v được thực hiện trên cơ sở tìm kiếm theo chiều sâu từ các đỉnh chưa được duyệt kề với v. Quá trình này được mô tả bằng thủ tục đệ quy sau: Procedure DFS(v) 24 NguyÔn Minh §øc - §HQG Hµ Néi
Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ (* Tìm kiếm theo chiều sâu trên đồ thị bắt đầu từ đỉnh v *) (* Các biến Chuaxet và Ke là biến toàn cuc *) Begin Xet_dinh(v); Chuaxet[v]:=False; For u ∈ Ke(v) do If Chuaxet[u] Then DFS(u); End; (* Chương trình chính thực hiện thủ tục *) BEGIN (* Khởi tạo biến toàn cục Chuaxet *) For v ∈ V do Chuaxet[v]:=True; (* Duyệt đồ thị *) For v ∈ V do If Chuaxet[v] Then DFS(v); END. Như vậy, với thuật toán trên đây rõ ràng mỗi lệnh gọi DFS(v) sẽ thực hiện duyệt qua tất cả các đỉnh cùng thành phần liên thông với đỉnh v, bởi vì sau mỗi khi xét đỉnh v là lệnh gọi đến thủ tục DFS đối với các đỉnh kề với v. Mặt khác, do mỗi khi thăm đỉnh v xong, biến Chuaxet[v] được gán giá trị False nên mỗi đỉnh sẽ được thăm đúng một lần. Thuật toán lần lượt sẽ tiến hành tìm kiếm từ các đỉnh chưa được xét đến, vì vậy nó sẽ duyệt được qua tất cả các đỉnh của đồ thị. (Kể cả đồ thị không liên thông). Dộ phức tạp tính toán của thuật toán được đánh giá như sau: Trước hết ta thây rằng số phép toán cần thực hiện trong hai chu trình của thuật toán (Hai vòng For ở chương trình chinh) có cỡ là n. Còn thủ tục DFS phải thực hiện không quá m lần. Do đó tổng số phép toán cần thực hiện trong các thủ tục này có cỡ là n+m. Vậy độ phức tạp tính toán của thuật toán là O(n+m). Ví dụ 1: Xét đồ thị vô hướng cho bởi hình dưới đây (Hình 3.1) 2 6 7 3 1 8 4 5 9 10 Hình 3.1 Giả sử danh sách kề của đồ thị được lưu như sau: 2 3 4 1: 1 3 2: 1 2 5 8 3: 1 9 10 4: 25 NguyÔn Minh §øc - §HQG Hµ Néi
Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ 3 8 5: 7 8 6: 6 8 7: 3 5 6 7 8: 4 10 9: 4 9 10: Khi đó thứ tự các đỉnh được duyệt theo thuật toán trên bắt đầu từ đỉnh 1 là: 1 2 3 5 8 6 7 4 9 10 Thuật toán tìm kiếm theo chiều sâu trên đồ thị có hướng cũng được thực hiện tương tự, trong trường hợp này thủ tục DFS(v) sẽ cho phép duyệt tất cả các đỉnh u của đồ thị mà từ v có đường đi tói u. Độ phức tạp tính toán của thuật toán trong trường hợp này vẫn là O(n+m). Ví dụ 2: Xét đồ thị có hướng cho bởi hình dưới đây (Hình 3.2) 2 1 5 7 9 3 4 6 8 Hình 3.2 Giả sử danh sách các đỉnh kề của đồ thị được lưu như sau: 3 1: 1 4 2: 3: 5 4: 7 8 5: 5 6: 2 9 7: 6 8: 9: Khi đó thứ tự các đỉnh được duyệt theo thuật toán tìm kiếm theo chiều sâu bắt đầu từ đỉnh 1 là: 132457986 3.2 Thuật toán tìm kiếm theo chiều rộng trên đồ thị (Breadth First Search) Tư tưởng chính của phương pháp tìm kiếm theo chiều rộng trên đồ thị có thể được hiểu như sau: Ban đầu tất cả các đỉnh của đồ thị là chưa được xét đến, ta sẽ bắt đầu việc tìm kiếm từ một đỉnh nào đó của đồ thị, giả sử đỉnh đó là v1. Khi duyệt đỉnh v1 ta sẽ để ý tới tất cả các đỉnh v11, v12, .., v1k 26 NguyÔn Minh §øc - §HQG Hµ Néi
Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ kề với đỉnh v1 mà chưa được xét đến để ngay sau đó lần lượt xét tới các đỉnh này, khi duyệt đỉnh v1i (i=1,2,..k) ta lại để ý tới tất cả các đỉnh kề với nó mà chưa được xét đến để rồi lần lượt xét đến các đỉnh đó. Qua trình sẽ cứ như vậy cho đến khi nào tất cả các đỉnh của đồ thị đều được xét hết. Ta có thể hình dung phương pháp này như hình ảnh của vết dầu loang, từ một điểm trên mặt phẳng dầu sẽ loang sang ngay các điểm lân cận với điểm đó. Với phương pháp này ta thấy rằng các đỉnh kề với một đỉnh của đồ thị sẽ được xếp hàng theo thứ tự để được lần lượt xét tới, do đó chúng ta có thể dùng cơ chế hàng đợi để thực hiện công việc này. Thủ tục mô tả phương pháp này như sau Procedure BFS(v) (* tìm kiếm theo chiều rộng bắt đầu từ đỉnh v *) (* Các biến Chuaxet, Ke là toàn cục *) Begin Queue : = φ Queue ⇐ v; (* Nạp v vào Queue *) Chuaxet[v]:=False; While Queue ≠ φ do Begin p ⇐ Queue; (* Lấy p ra khỏi Queue *) Xet_dinh(p); For u ∈ Ke(p) do If Chuaxet[u] then Begin Queue ⇐ u; Chuaxet[u]:=False; End; End; End; (* Chương trình chính thực hiện thủ tục *) BEGIN (* Khởi tạo biến toàn cục Chuaxet *) For v ∈ V do Chuaxet[v]:=True; (* Duyệt các đỉnh *) For v ∈ V do If Chuaxet[v] then BFS(v); END. Với thuật toán này ta cũng thấy rằng mỗi lệnh gọi BFS(v) sẽ thực hiện duyệt qua các đỉnh cùng thành phần liên thông với đỉnh v. Thủ tục BFS sẽ được thực hiện lần lượt với các đỉnh chưa được duyệt của đồ thị, do đó nó sẽ duyệt hết tất cả các đỉnh của đồ thị. Mặt khác, mỗi khi duyệt xong đỉnh v, biến Chuaxet[v] cũng được gán giá trị False nên mỗi đỉnh sẽ được thăm đúng một lần. Lập luận tương tự thuật toán tìm kiếm theo chiều sâu ta cũng có được độ phức tạp tính toán của thuật toán này là O(n+m). Ví dụ 3 Xét đồ thị vô hướng cho ở ví dụ 1 (hình 3.1) Khi đó thứ tự các đỉnh được duyệt theo thuật toán tìm kiếm theo chiều rộng sẽ là: 1 2 3 4 5 8 9 10 6 7 27 NguyÔn Minh §øc - §HQG Hµ Néi
Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ Ví dụ 4 Xét đồ thị có hướng cho ở ví dụ 2 (Hình 2) Khi đó thứ tự các đỉnh được duyệt theo thuật toán tìm kiếm theo chiều rộng sẽ là: 1324578 96 Dưới đây là chương trình cài đặt hai thuật toán tìm kiếm theo chiều sâu và tìm kiếm theo chiều rộng bằng ngôn ngữ lập trình C. Chương trình xử lý trên đồ thị được cho bởi danh sách kề. //---------------------------------------------------------------------------- // huong trinh cai dat cac thuat toan tim kiem tren do thi // Depth First Search - Breadth First Search //---------------------------------------------------------------------------- #include #include #include #define VMAX 100 //So dinh toi da cho mot do thi typedef struct pp //Cau truc tu tro { int v; struct pp *next; }Link; Link *Ke[VMAX]; //Danh sach ke cua do thi int chuaxet[VMAX]; //Bien mang dung de danh dau cac dinh da xet Link *Queue; //Hang doi luu thu tu cac dinh se xet int n; //So dinh cua do thi //-------------------------------------------------------------------------- // Ham nhap danh sach ke cua do thi co n dinh //-------------------------------------------------------------------------- void nhap_dsk(Link *Ke[], int n) { int i,v; Link *pd,*p; //Khoi tao mang cac danh sach cac dinh ke cua cac dinh for(i=1;iv=i; Ke[i]->next = NULL; } //Nhap danh sach cac dinh ke cua cac dinh for(i=1;i
Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ scanf("%d",&v); if(v==0) break; if(pd == NULL) { pd = (Link*)malloc(sizeof(Link)); p=pd; } else { p->next = (Link*)malloc(sizeof(Link)); p=p->next; } p->v=v; p->next = NULL; } Ke[i]->next = pd; } } //-------------------------------------------------------------------------- // Ham hien thi danh sach ke cua do thi co n dinh //-------------------------------------------------------------------------- void in_dsk(Link *Ke[], int n) { int i; Link *pd; printf("\nDanh sach ke cua cac dinh cua do thi:\n"); printf("\n ------------------\n"); for(i=1;iv); pd = Ke[i]->next; while(pd!=NULL) { printf("%5d",pd->v); pd=pd->next; } } } //-------------------------------------------------------------------------- // Ham nap mot phan tu (mot dinh ) vao hang doi //-------------------------------------------------------------------------- void Push(Link *u) { Link *q,*p; q=(Link*)malloc(sizeof(Link)); q->v=u->v; q->next=NULL; if(Queue==NULL) 29 NguyÔn Minh §øc - §HQG Hµ Néi
Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ Queue = q; else { p=Queue; while(p->next!=NULL) p=p->next; p->next = q; } } //-------------------------------------------------------------------------- // Ham lay mot phan tu trong hang doi ra //-------------------------------------------------------------------------- int Pop() { if(Queue==NULL) return 0; //Quee rong! Link *p; p=Queue; Queue=p->next; int t=p->v; free(p); //Giai phong p return t; } //-------------------------------------------------------------------------- // Ham de quy tim kiem theo chieu sau bat dau tu mot dinh //-------------------------------------------------------------------------- void dfs(Link *u) { printf("%3d",u->v); chuaxet[u->v]=0; Link *p = Ke[u->v]->next; while(p!=NULL) { if(chuaxet[p->v]) dfs(p); p=p->next; } } //-------------------------------------------------------------------------- // Ham tim kiem theo chieu rong bat dau tu mot dinh //-------------------------------------------------------------------------- void bfs(Link *u) { Queue=NULL; //Khoi tao hang doi Push(u); chuaxet[u->v]=0; while(Queue!=NULL) { int u; 30 NguyÔn Minh §øc - §HQG Hµ Néi
Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ u=Pop(); printf("%5d",u); Link *p=Ke[u]->next; while(p!=NULL) { if(chuaxet[p->v]) { Push(p); chuaxet[p->v]=0; } p=p->next; } } } //-------------------------------------------------------------------------- // Ham in tieu de cua chuong trinh //-------------------------------------------------------------------------- void tieu_de() { printf("\n CHUONG TRINH CAI DAT CAC THUAT TOAN TIM KIEM TREN DO THI"); printf("\n --------------***--------------\n\n"); } //-------------------------------------------------------------------------- // Ham hien thi Menu chon chuc nang cua chuong trinh //-------------------------------------------------------------------------- char menu() { printf("\n Menu chon chu nang"); printf("\n ---***---\n"); printf("\n\n 1. Nhap do thi cho boi danh sach ke"); printf("\n\n 2. Hien thi danh sach ke cua do thi"); printf("\n\n 3. Tim kiem theo chieu sau tren do thi"); printf("\n\n 4. Tim kiem theo chieu rong tren do thi"); printf("\n\n 5. Ket thuc chuong trinh"); printf("\n\n ----------------------------------------"); printf("\n\n Ban chon:"); char ch=getche(); return ch; } //-------------------------------------------------------------------------- // Chuong trinh chinh //-------------------------------------------------------------------------- void main() { int kt=0,i; char ch; do { clrscr(); tieu_de(); 31 NguyÔn Minh §øc - §HQG Hµ Néi
Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ ch = menu(); switch(ch) { case '1': //Nhap danh sach ke cua do thi clrscr(); tieu_de(); kt=1; printf("\n\n1.Nhap danh sach ke cua do thi"); printf("\n------------------------------\n\n"); printf("\n\nSo dinh cua do thi n ="); scanf("%d",&n); nhap_dsk(Ke,n); printf("\n\n\n\n--------------------------------"); printf("\nGo mot phim bat ky de tro ve menu chon chuc nang!"); getch(); break; case '2': //Hien thi danh sach ke cua do thi clrscr(); tieu_de(); printf("\n\n2.In danh sach ke cua do thi"); printf("\n----------------------------\n\n"); if(kt) in_dsk(Ke,n); else printf("\nDo thi chua duoc nhap vao!"); printf("\n\n\n\n--------------------------------"); printf("\nGo mot phim bat ky de tro ve menu chon chuc nang!"); getch(); break; case '3': //Tim kiem theo chieu sau tren do thi clrscr(); tieu_de(); printf("\n\n3.Tim kiem theo chieu sau tren do thi"); printf("\n-------------------------------------\n\n"); if(kt) { //Khoi toa bien chuaxet; for(i=1;i
Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ case '4': //Tim kiem theo chieu rong tren do thi clrscr(); tieu_de(); printf("\n\n4.Tim kiem theo chieu rong tren do thi"); printf("\n--------------------------------------"); if(kt) { //Khoi toa bien chuaxet; for(i=1;i
Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ Procedure DFS(u) Begin Chuaxet[u]:=False; For v ∈ Ke(u) do If Chuaxet[v] then Begin Truoc[v]:= u; DFS(v); End; End; Thủ tục tìm kiếm theo chiều rộng áp dụng cho việc tìm đường đi: Procedure BFS(u) Begin Queue : = φ Queue ⇐ v; Chuaxet[u]:=False; While Queue ≠ φ do Begin p ⇐ Queue; For v ∈ Ke(p) do If Chuaxet[v] then Begin Queue ⇐ v; Chuaxet[v]:=False; Truoc[v]:=p; End; End; End; Theo cách trên, đường đi cần tìm sẽ là: v ← t1 := Truoc[v] ← t 2 := Truoc[t1 ] ← ... ← u Ví dụ 5 Xét đồ thị cho bởi hình dưới đây (Hình 3.3) 2 6 5 8 1 3 7 4 Hình 3.3 Nếu áp dụng tìm đường đi theo thuật toán tìm kiếm theo chiều sâu bắt đầu từ đỉnh 1 ta sẽ có: 34 NguyÔn Minh §øc - §HQG Hµ Néi
Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ Truoc[2]=1, Truoc[3]=5, Truoc[4]=5, Truoc[5]=2, Truoc[6]=5, Truoc[7]=8, Truoc[8]=6 Vậy đường đi tìm theo thuật toán tìm kiếm theo chiều sâu từ đỉnh 1 đến đỉnh 8 sẽ là: 1← 2 ← 5 ← 6 ←8 Nếu áp dụng tìm đường đi theo thuật toán tìm kiếm theo chiều rộng bắt đầu từ đỉnh 1 ta sẽ có: Truoc[2]=1, Truoc[3]=1, Truoc[4]=1, Truoc[5]=2, Truoc[6]=5, Truoc[7]=5, Truoc[8]=5 Vậy đường đi tìm theo thuật toán tìm kiếm theo chiều sâu từ đỉnh 1 đến đỉnh 8 sẽ là: 1← 2 ← 5 ←8 Chú ý Xét theo cách duyệt các đỉnh của đồ thị thì ta có thể suy ra được đường đi tìm được theo thuật toán tìm kiếm theo chiều rộng là đường đi có số cạnh ít nhất. 3.3.2 Bài toán kiểm tra tính liên thông của đồ thị Bài toán Hãy cho biết đồ thị gồm bao nhiêu thành phần liên thông và các đỉnh trong từng thành phần liên thông của đồ thị Do hai thủ tục DFS(u) và BFS(u) đều cho phép ta duyệt qua tất cả các đỉnh thuộc cùng một thành phần liên thông với đỉnh u. Do đó số thành phần liên thông của đồ thị chính bằng số lần ta gọi tới thủ tục DFS (hoặc BFS) khi thực hiện việc duyệt qua tất cả các đỉnh của đồ thị. Vậy để giải quyết bài toán trên ta có thể áp dụng một trong hai thủ tục DFS hoặc BFS, trong đó ta cần phải có một biến Sotplt dùng để đếm số thành phần liên thông (số lần gọi thủ tục) và một biến mảng Thanhplt[] đánh dấu các đỉnh thuộc cùng một thành phần liên thông với nhau (có thể dùng ngay mảng Chuaxet[]). Các thủ tục DFS và BFS có thể được sửa lại như sau: Thủ tục DFS: Procedure DFS(u) (* Biến Sotplt và Thanhplt[] là toàn cục *) Begin Chuaxet[u]:=False; Thanhplt[u]:=Sotplt; For v ∈ Ke(u) do If Chuaxet[v] then DFS(v); End; Thủ tục BFS: Procedure BFS(u) (* Bien Sotplt và Thanhplt[] là toàn cục *) Begin Queue : = φ Queue ⇐ v; Chuaxet[u]:=False; Thanhplt[u]:=Sotplt; While Queue ≠ φ do 35 NguyÔn Minh §øc - §HQG Hµ Néi
Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ Begin p ⇐ Queue; For v ∈ Ke(p) do If Chuaxet[v] then Begin Queue ⇐ v; Chuaxet[v]:=False; Thanhplt[v]:=Sotplt; End; End; End; Khi đó chương trình chính sẽ là: BEGIN Sotplt=0; For v ∈ V do Chuaxet[v]:=True; For v ∈ V do If Chuaxet[v] Then Begin Sotplt:=Sotplt+1; DFS(v); (* BFS(v) *) End; END. Dưới đây là chương trình được viết bằng ngôn ngữ C để giải quyết hai bài toán nói trên //-------------------------------------------------------------------------------------- // Chuong trinh cai dat ung dung cua thuat toan tim kiem tren do thi // ( Tim duong di va kiem tra tinh lien thong ) //-------------------------------------------------------------------------------------- #include #include #include #define VMAX 100 //So dinh toi da cho mot do thi typedef struct pp //Cau truc tu tro { int v; struct pp *next; }Link; Link *Ke[VMAX]; //Danh sach ke cua do thi int chuaxet[VMAX]; //Bien mang dung de danh dau cac dinh da xet Link *Queue; //Hang doi dung cho thuat toan tim kiem theo chieu rong int sTruoc[VMAX]; //Duong di tim theo thuat tim kiem theo chieu sau int rTruoc[VMAX]; //Duong di tim theo thuat tim kiem theo chieu rong int sotplt; //So thanh phan lien thong int n; //So dinh cua do thi //---------------------------------------------------------------------------------- // Ham nhap danh sach ke cua do thi co n dinh //---------------------------------------------------------------------------------- 36 NguyÔn Minh §øc - §HQG Hµ Néi
Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ void nhap_dsk(Link *Ke[], int n) { int i,v; Link *pd,*p; //Khoi tao mang cac danh sach cac dinh ke cua cac dinh for(i=1;iv=i; Ke[i]->next = NULL; } //Nhap danh sach cac dinh ke cua cac dinh for(i=1;inext = (Link*)malloc(sizeof(Link)); p=p->next; } p->v=v; p->next = NULL; } Ke[i]->next = pd; } } //-------------------------------------------------------------------------- // Ham hien thi danh sach ke cua do thi co n dinh //-------------------------------------------------------------------------- void in_dsk(Link *Ke[], int n) { int i; Link *pd; printf("\nDanh sach ke cua cac dinh cua do thi:\n"); printf("\n ------------------"); for(i=1;iv); 37 NguyÔn Minh §øc - §HQG Hµ Néi
Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ pd = Ke[i]->next; while(pd!=NULL) { printf("%5d",pd->v); pd=pd->next; } } } //-------------------------------------------------------------------------- // Ham nap mot phan tu (mot dinh ) vao hang doi //-------------------------------------------------------------------------- void Push(int t) { Link *q,*p; q=(Link*)malloc(sizeof(Link)); q->v=t; q->next=NULL; if(Queue==NULL) Queue = q; else { p=Queue; while(p->next!=NULL) p=p->next; p->next = q; } } //-------------------------------------------------------------------------- // Ham lay mot phan tu trong hang doi ra //-------------------------------------------------------------------------- int Pop() { if(Queue==NULL) return 0; //Quee rong! Link *p; p=Queue; Queue=p->next; int t=p->v; free(p); //Giai phong p return t; } //---------------------------------------------------------------------------------- // Ham de quy tim kiem theo chieu sau bat dau tu mot dinh // ( Ap dung de tim duong di giua hai dinh va kiem tra lien thong) //---------------------------------------------------------------------------------- void dfs(int u) { chuaxet[u]=sotplt; Link *p = Ke[u]->next; 38 NguyÔn Minh §øc - §HQG Hµ Néi
Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ while(p!=NULL) { if(chuaxet[p->v]==1) { sTruoc[p->v]=u; dfs(p->v); } p=p->next; } } //---------------------------------------------------------------------------------- // Ham tim kiem theo chieu rong bat dau tu mot dinh // ( Ap dung de tim duong di giua hai dinh va kiem tra lien thong) //---------------------------------------------------------------------------------- void bfs(int t) { Queue=NULL; //Khoi tao hang doi Push(t); chuaxet[t]=sotplt; while(Queue!=NULL) { int u; u=Pop(); Link *p=Ke[u]->next; while(p!=NULL) { if(chuaxet[p->v]==1) { Push(p->v); chuaxet[p->v]=sotplt; rTruoc[p->v]=u; } p=p->next; } } } //----------------------------------------------------------------------------- // Ham tim duong di giua hai dinh bat ky tren do thi // Ap dung thuat toan tim kiem theo chieu sau //----------------------------------------------------------------------------- void dd_dfs() { int dau, cuoi; printf("\n\nTim duong di tu dinh:"); scanf("%d",&dau); printf("den dinh:"); scanf("%d",&cuoi); dfs(dau); if(chuaxet[cuoi]==1) printf("\n\nKhong co duong di tu dinh %d den dinh %d tren do thi!",dau,cuoi); else 39 NguyÔn Minh §øc - §HQG Hµ Néi
Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ { printf("\n\nDuong di tu dinh %d den dinh %d tren do thi la:\n",dau,cuoi); printf("%d
Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ sotplt++; dfs(Ke[i]->v); //co the dung bfs(Ke[i]->v) thay cho dfs(Ke[i]->v) } if(sotplt==2) printf("\n\nDo thi la lien thong!"); else { printf("\n\nDo thi la khong lien thong!"); printf("\n\nSo thanh phan lien thong cua do thi la %d",sotplt-1); for(int j=2;j
Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ char ch; do { clrscr(); tieu_de(); ch = menu(); switch(ch) { case '1': //Nhap danh sach ke cua do thi clrscr(); tieu_de(); kt=1; printf("\n\n1.Nhap danh sach ke cua do thi"); printf("\n------------------------------\n\n"); printf("\n\nSo dinh cua do thi n ="); scanf("%d",&n); nhap_dsk(Ke,n); printf("\n\n\n\n--------------------------------"); printf("\nGo mot phim bat ky de tro ve menu chon chuc nang!"); getch(); break; case '2': //Hien thi danh sach ke cua do thi clrscr(); tieu_de(); printf("\n\n2.In danh sach ke cua do thi"); printf("\n----------------------------\n\n"); if(kt) in_dsk(Ke,n); else printf("\n\nDo thi chu duoc nhap vao!"); printf("\n\n\n\n--------------------------------"); printf("\nGo mot phim bat ky de tro ve menu chon chuc nang!"); getch(); break; case '3': //Tim duong di - theo thuat tk chieu sau clrscr(); tieu_de(); printf("\n\n3.Tim duong di - theo thuat tk chieu sau"); printf("\n-----------------------------------------\n\n"); if(kt) { //Khoi toa bien chuaxet; for(i=1;i
Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ break; case '4': //Tim duong di - theo thuat tk chieu rong clrscr(); tieu_de(); printf("\n\n4.Tim duong di - theo thuat tk chieu rong"); printf("\n-----------------------------------------\n\n"); if(kt) { //Khoi toa bien chuaxet; for(i=1;i

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.