Giáo án môn Lý thuyết đồ thị

4 5 7 9 8 6 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 Hình 3.2 Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ NguyÔn Minh §øc - §HQG Hµ Néi 27 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 Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ NguyÔn Minh §øc - §HQG Hµ Néi 28 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à: 1 3 2 4 5 7 8 9 6 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;i<=n;i++) { Ke[i] = (Link*)malloc(sizeof(Link)); Ke[i]->v=i; Ke[i]->next = NULL; } //Nhap danh sach cac dinh ke cua cac dinh for(i=1;i<=n;i++) { pd = NULL; printf("\nNhap cac dinh ke voi dinh %d (nhap 0 de ket thuc!):",i); while(1) { Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ NguyÔn Minh §øc - §HQG Hµ Néi 29 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;i<=n;i++) { printf("\n Danh sach cac dinh ke cua dinh %d:",Ke[i]->v); 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) Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ NguyÔn Minh §øc - §HQG Hµ Néi 30 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; Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ NguyÔn Minh §øc - §HQG Hµ Néi 31 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(); Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ NguyÔn Minh §øc - §HQG Hµ Néi 32 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<=n;i++) chuaxet[i]=1; //Ket qua tim kiem theo chieu sau printf("\n\nThu tu cac dinh duoc xet theo chieu xau:\n\n"); for(i=1;i<=n;i++) if(chuaxet[i]) dfs(Ke[i]); } 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; Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ NguyÔn Minh §øc - §HQG Hµ Néi 33 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<=n;i++) chuaxet[i]=1; //Ket qua tim kiem theo chieu rong printf("\n\nThu tu cac dinh duoc xet theo chieu rong:\n\n"); for(i=1;i<=n;i++) if(chuaxet[i]) bfs(Ke[i]); } 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 '5': //Ket thuc chuong trinh printf("\n\nXin cam on ban da su dung chuong trinh!"); getch(); break; } }while(ch!='5'); } 3.3 Ứng dụng của thuật toán tìm kiếm trên đồ thị Trong mục này chúng ta sẽ thực hiện ứng dụng hai thuật toán tìm kiếm trên đồ thị đã trình bầy ở trên vào việc giải hai bài toán cơ bản trên đồ thị là bài toán tìm một đường đi nối hai đỉnh bất kỳ của đồ thị và bài toán kiểm tra tính liên thông của đồ thị (xác định số thành phần liên thông của đồ thị). 3.3.1 Bài toán tìm đường đi giữa hai đính bất kỳ của đồ thị Bài toán Giả sử u và v là hai đỉnh nào đó của đồ thị G = (V,E), Hãy tìm đường đi từ đỉnh u tới đỉnh v. Như chúng ta đã biết hai thủ tục DFS(u) và BFS(u) sẽ cho phép 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. Vì vậy sau khi thực hiện xong thủ tục mà biến Chuaxet[v] vẫn bằng True (đỉnh v chưa được duyệt) thì có nghĩa là không có đường đi từ u tới v, ngược lại nếu Chuaxet[v] = False thì v thuộc cùng một thành phần liên thông với u, hay tồn tại một đường đi từ u tới v. Trong trường hợp này, để ghi lại đường đi từ u tưới v ta có thể dùng một biến mảng Truoc[v] để lưu lại các đỉnh đi qua trước đỉnh v trong đường đi từ u tới v. Khi đó hai thủ tục DFS(u) và BFS(u) được sửa lại như sau: Thủ tục đệ quy tìm kiếm theo chiều sâu áp dụng cho việc tìm đường đi: Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ NguyÔn Minh §øc - §HQG Hµ Néi 34 1 2 3 4 5 7 6 8 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à: utTruoctvTruoctv ←←=←=← ...][:][: 121 Ví dụ 5 Xét đồ thị cho bởi hình dưới đây (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ó: Hình 3.3 Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ NguyÔn Minh §øc - §HQG Hµ Néi 35 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à: 86521 ←←←← 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à: 8521 ←←← 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 Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ NguyÔn Minh §øc - §HQG Hµ Néi 36 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 //---------------------------------------------------------------------------------- Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ NguyÔn Minh §øc - §HQG Hµ Néi 37 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;i<=n;i++) { Ke[i] = (Link*)malloc(sizeof(Link)); Ke[i]->v=i; Ke[i]->next = NULL; } //Nhap danh sach cac dinh ke cua cac dinh for(i=1;i<=n;i++) { pd = NULL; printf("\nNhap cac dinh ke voi dinh %d (nhap 0 de ket thuc!):",i); while(1) { 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 ------------------"); for(i=1;i<=n;i++) { printf("\n Danh sach cac dinh ke cua dinh %d:",Ke[i]->v); Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ NguyÔn Minh §øc - §HQG Hµ Néi 38 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; Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ NguyÔn Minh §øc - §HQG Hµ Néi 39 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 Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ NguyÔn Minh §øc - §HQG Hµ Néi 40 { printf("\n\nDuong di tu dinh %d den dinh %d tren do thi la:\n",dau,cuoi); printf("%d<--",cuoi); int j=cuoi; while(sTruoc[j]!=dau) { printf("%d<--",sTruoc[j]); j=sTruoc[j]; } printf("%d",dau); } } //------------------------------------------------------------------------------ // Ham tim duong di giua hai dinh bat ky tren do thi // Ap dung thuat toan tim kiem theo chieu rong //------------------------------------------------------------------------------ void dd_bfs() { int dau, cuoi; printf("\n\nTim duong di tu dinh:"); scanf("%d",&dau); printf("den dinh:"); scanf("%d",&cuoi); bfs(dau); if(chuaxet[cuoi]==1) printf("\n\nKhong co duong di tu dinh %d den dinh %d tren do thi!",dau,cuoi); else { printf("\n\nDuong di tu dinh %d den dinh %d tren do thi la:\n",dau,cuoi); printf("%d<--",cuoi); int j=cuoi; while(rTruoc[j]!=dau) { printf("%d<--",rTruoc[j]); j=rTruoc[j]; } printf("%d",dau); } } //-------------------------------------------------------------------------- // Ham kiem tra tinh lien thong cua do thi //-------------------------------------------------------------------------- void kiemtra_lt() { sotplt=1; for(int i=1;i<=n;i++) chuaxet[i]=1; for(i=1;i<=n;i++) if(chuaxet[i]==1) { Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ NguyÔn Minh §øc - §HQG Hµ Néi 41 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<=sotplt;j++) { printf("\n\nThanh phan lien thong thu %d gom cac dinh:",j); for(int k=1;k<=n;k++) if(chuaxet[k]==j) printf("%5d",k); } } } //-------------------------------------------------------------------------- // Ham in tieu de cua chuong trinh //-------------------------------------------------------------------------- void tieu_de() { printf("\n CHUONG TRINH TIM DUONG DI VA KIEM TRA TINH LIEN THONG"); 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 duong di - theo thuat tk chieu sau"); printf("\n\n 4. Tim duong di - theo thuat tk chieu rong"); printf("\n\n 5. Kiem tra tinh lien thong cua do thi"); printf("\n\n 6. Ket thuc chuong trinh"); printf("\n\n ----------------------------------------"); printf("\n\n Ban chon:"); char ch=getche(); return ch; } //-------------------------------------------------------------------------- // Chuong trinh chinh //-------------------------------------------------------------------------- void main() { int i,kt=0; Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ NguyÔn Minh §øc - §HQG Hµ Néi 42 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<=n;i++) chuaxet[i]=1; dd_dfs(); } else printf("\n\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(); Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ NguyÔn Minh §øc - §HQG Hµ Néi 43 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---------