Bài 11-Cài đặt đồ thị và duyệt đồ thị BFS, DFS

DUYET MA TRAN DFS, BFS

 1.Nhap ma tran tu ban phim

 2.Nhap ma tran tu tep

 3.Hien thi ma tran

 4.Duyet ma tran DFS(v)

 ESC ket thuc chuong trinh

Dothi1.txt LUU MA TRAN KE

5

0 1 0 1 0

1 0 0 0 1

0 0 0 1 1

1 0 1 0 1

0 1 1 1 0

 Duyet theo chieu sau DFS

Ban bat dau duyet tu dinh nao :3

  1. 4  1  2  5

 

DFS.cpp

 

/* Phan duyet theo chieu rong BFS(), cac ban sinh vien cai dat tiep vao chuong trinh nay */

 

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <conio.h>

#include <alloc.h>

#define MAX 100

typedef struct MatranKe

{     int A[MAX][MAX];

      int n;

};

MatranKe G; // G ma tran ke,G.A[i][i]=0; moi 0< i<=n;

int chuaxet[MAX];

int i,j;

 

// C¸c b¹n cÇn ph¶i ®Þnh nghÜa mét hµng ®îi vµ c¸c phÐp to¸n cña nã nh­ thªm vµo lÊy ra, ë

// ®©y ®Ó ¸p dông cho BFS()

 

void NhapGtuTep(char s[30]);  void NhapG();

void HienthiG();              void Menu();

void DFS(int v);              void BFS(int v);  void MakeNull(int *);              

 

 

 

/* chuong trinh chinh */

void main()

{  char ch; char tentep[20]; int v;

   do{  //clrscr();

      Menu();

      ch=getch();

      switch(ch)

      {

       case '1': printf("\n\n\tNhap ten tep tin:");

               gets(tentep);

               NhapGtuTep(tentep);

               getch(); break;

       case '2': HienthiG();

               getch(); break;

       case '4': if(G.n>0){

                     printf("\n\nDuyet theo chieu sau DFS");

                     printf("\nBan bat dau duyet tu dinh nao :");

                     MakeNull(chuaxet);

                     scanf("%d",&v);   v = abs(v);

                     if (v <= G.n)  DFS(v);

                     else printf("Nhap lai so hieu dinh v:<= %d", G.n);

               }

               else printf("\nBan phai nhap do thi");

               getch(); break;

      }

   }while (ch!=27);

}

 

void MakeNull(int *chuaxet)

{

  for(int i=1; i<=G.n;i++) chuaxet[i]=0;

}

void NhapGtuTep(char s[30])

{  FILE *fp;

   char tentep[20];

   strcpy(tentep,s);

   if ((fp = fopen(tentep,"rt")) == NULL){

         fprintf(stderr, "Khong mo duoc tep tin %s",tentep);

         return;

   }

   int n,i,j,x;

   fscanf(fp,"%d",&n);

   G.n=n;

   for(i=1; i<=n; i++)

      for(j=1;j<=n;j++){

           fscanf(fp,"%d",&x);

           G.A[i][j]=x;

        }

   fclose(fp);

   printf("\nDa doc xong tep tin...");

}

void NhapG()

{

  // Phan nay danh cho cac ban sinh vien

}

 

void HienthiG()

{

  int n = G.n;

  int i,j;

  printf("\n\n MA TRAN KE \n");

  for(i=1; i<=n; i++){

     printf("\n");

     for(j=1;j<=n;j++) printf("%3d",G.A[i][j]);

  }

}

// Duyet theo chieu sau

void DFS(int v)

{ int w;

  printf("%3d",v);

  chuaxet[v]=1;

  for(w=1; w<=G.n ; w++)

      if(G.A[v][w]==1)

        if(chuaxet[w]==0 ) DFS(w);

}

void Menu()

{

  printf("\n\n DUYET MA TRAN ");

  printf("\n 1.Nhap ma tran tu ban phim");

  printf("\n 2.Nhap ma tran tu tep ");

  printf("\n 3.Hien thi ma tran");

  printf("\n 4.Duyet ma tran DFS(v)");

  printf("\n 5.Duyet ma tran BFS(v)");

  printf("\n ESC ket thuc chuong trinh");

}

Tham khảo: Nguyễn Trường Xuân và các tác giả, Lý thuyết đồ thị và ứng dụng, nxb Giáo dục Việt Nan, 2017. 

Bình luận

Bài viết khác

Bài 16- Thuật toán Ford -Fulkerson

Thuật toán Ford - Fulkerson  Việc chứng minh định lý luồng cực đại - lát cắt cực tiểu cho ta một thuật toán tìm luồng cực đại (thuật toán Ford- Fulkerson)

Bài 15-Cài đặt thuật toán Dijkstra

Năm 1959, Edsger W. Dijkstra đưa ra một thuật toán rất hiệu quả để giải bài toán đường đi ngắn nhất. Thuật toán thực hiện việc gán và giảm giá trị của nhãn tại mỗi đỉnh của đồ thị.

Bài 14-Thuật toán Prim

Thuật toán Prim do Robert Prim đưa ra vào năm 1957, ý tưởng chính của nó là lần lượt ghép vào cây khung các cạnh có trọng số tối thiểu liên thuộc với một đỉnh của cây mà không tạo ra chu trình trong cây. Thuật toán sẽ dừng khi có được n - 1 cạnh vào cây. Dưới đây là mô tả các bước của thuật toán Prim.

Bài 13-Cài đặt thuật toán Kruskal tìm cây khung tối thiểu

File dữ liệu về đồ thị dạng text;

ĐỐI TÁC CỦA CHÚNG TÔI