intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

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

Chia sẻ: Nguyen Kien | Ngày: | Loại File: PDF | Số trang:10

Thêm vào BST
Báo xấu
164
lượt xem 55
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

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

Chủ đề:

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

Lưu

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

  1. 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
  2. C u trúc d li u cho th tr li th Ví 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
  3. C u trúc d li u cho th tr li th Danh 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
  4. C u trúc d li u cho th tr li th Bài t p: 1. Bi u di n danh sách k cho th 1 2. Bi u di n ma tr n k cho th sau
  5. C u trúc d li u cho th tr li th Cài t ma tr n k : #define max 100 struct Graph { int n; int a[max][max]; }; nh d ng d li u: D li u vào ma tr n k ư c lư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
  6. 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”);
  7. 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;i
  8. THU T TOÁN DUY T THU TO TH TH
  9. 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)
  10. Duy t theo chi u sâu Duy theo sâu Duy t theo chi u sâu: M i l n duy t m t nh ta duy t n t n cùng m i nhánh r i m i chuy n sang duy t nhánh khác. Ví d : 3 D 2 4 B H 1 5 A E 7 G 8 C 6 F Th t duy t: A, B, D, H, E, F, G, C
ADSENSE

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.

 

Đồng bộ tài khoản
703=>1