Cấu trúc dữ liệu và giải thuật (phần 16)

Tiếp tục với các cấu trúc dữ liệu trong đồ thị cách thể hiện dữ liệu thông qua đồ thì như thể hiện ma trận kề bằng đồ thị và một số ma trận khác cơ bản
Nội dung trích xuất từ tài liệu:
Cấu trúc dữ liệu và giải thuật (phần 16) C u trúc d li u cho th tr li th Ma tr n k :- Bi u di n th G=(V,E) b ng ma tr n k |V|v i N hàng, N c t v i các giá tr 0,1|V|= 0 N u không t n t i c nh gi a vivj 1 N u t n t i c nh gi a vivj- th có th có tr ng s : Giá tr c a ma tr n k g m tr ng s c a các c nh C u trúc d li u cho th tr li thVí d : Bi u di n ma tr n k cho các th sau 1 2 3 4 5 1 2 3 4 5 1 1 0 1 1 0 0 0 1 1 0 0 2 2 1 0 1 1 0 1 0 0 0 0 3 3 1 1 0 0 1 0 1 0 0 0 4 4 0 1 0 0 1 0 0 1 0 1 5 5 0 0 1 1 0 0 1 0 1 0 C u trúc d li u cho th tr li thDanh sách k : th G=(V,E) b ng danh sách k |V| là- Bi u di n m t m ng 1 chi u có size N, trong ó m i nh tương ương 1 danh sách liên k t C u trúc d li u cho th tr li thBài t p:1. Bi u di n danh sách k cho th 12. Bi u di n ma tr n k cho th sau C u trúc d li u cho th tr li thCài t ma tr n k :#define max 100struct Graph{ int n; int a[max][max];}; nh d ng d li u: D li u vào ma tr n k ư clưu file: 1. Dòng u tiên: s nh c a th 2. M i dòng ch a n s nguyên ng v i giá tr trong ma tr n k C u trúc d li u cho th tr li th c ma tr n k t file:void Matranke (Graph &g){ char file[128]; printf(“Tap tin nguon (Dothi.txt)”); gets(file); if (strcmp(file,””)==0) strcpy(file,”Dothi.txt”); FILE *f; f = fopen(file,”rt”); C u trúc d li u cho th tr li th if ( f==NULL) { printf(“Khong mo duoc file”); exit(0); } fscanf(f,”%d”,&g.n); for (int i=0;iTHU T TOÁN DUY TTHU TO TH TH T ng quan ng Duy t hay tìm ki m trên th : ghé qua m i nh trong th m t cách có h th ng th không ph thu c vào hư ng c a- Duy t c nh Có 2 cách duy t th : - Duy t theo chi u sâu ( Depth-first) - Duy t theo chi u r ng (Breadth-first) Duy t theo chi u sâu Duy theo sâuDuy t theo chi u sâu: M i l n duy t m t nh taduy t n t n cùng m i nhánh r i m i chuy n sangduy t nhánh khác.Ví d : 3 D 2 4 B H1 5 A E 7 G 8 C 6 F Th t duy t: A, B, D, H, E, F, G, C