Chương 4: Độ phức tạp của các giải thuật đồ thị

Chia sẻ: Ba Xoáy | Ngày: | Loại File: PDF | Số trang:0

Thêm vào BST

Báo xấu

69
lượt xem 4
download

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

Một đồ thị là một tập các đỉnh và các cạnh. Các đỉnh là những đối tượng đơn mà có thể có tên và có một số tính chất khác và cạnh là đường kết nối giữa hai đỉnh. Một lối đi từ X đến Y trong một đồ thị là một danh sách những đỉnh mà những đỉnh kế tiếp nhau được kết nối nhờ vào những cạnh trên đồ thị

Chủ đề:

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

Lưu

Nội dung Text: Chương 4: Độ phức tạp của các giải thuật đồ thị

Ch ng 4 ph c t p c a các gi i thu t th 1
N i dung 1. Các gi i thu t th c n b n 2. th có tr ng s 3. th có h ng 2
1.Các gi i thu t th c n b n Có nhi u bài toán c nh ngh a theo it ng và các k t n i gi a các i t ng y. Mt th là m t i t ng toán h c mà mô t nh ng bài toán nh v y. Các ng d ng trong các lãnh v c: Giao thông Vi n thông i nl c M ng máy tính C s d li u Trình biên d ch Các h i u hành Lý thuy t th 3
M t thí d A H I B C G D E J K F L M Hình 4.1a M t th thí d 4
Thu t ng th là m t t p các nh và các c nh. Các nh là Mt nh ng i t ng n mà có th có tên và có m t s tính ch t khác và c nh là ng k t n i gi a hai nh. M t l i i t x n y trong m t th là m t danh sách nh ng nh mà nh ng nh k ti p nhau c k t n i nh vào nh ng c nh trên th . th là liên thông n u có m t l i i t m i nút n Mt th mà không liên thông m t nút khác trong th . M t thì bao g m nhi u thành ph n liên thông. M tl i i n là m t l i i mà trên ó không có nh nào l p l i. 5
Thu t ng (tt.) M t chu trình (cycle ) là m t l i i n ngo i tr nh u tiên và nh cu i cùng trùng nhau (m t l i i t m t nh quay v chính nó). c g i là cây (tree). M t Mt th không có chu trình c g i là r ng ( forest ). nhóm các cây không liên thông Cây bao trùm c a m t th là m t th con mà ch a t t c các nh trong cây nh ng m t s c nh ch m n m i nh. G is nh trong m t th là V, s c nh là E, s c nh c a th có th có t 0 n V (V-1)/2. (Ch ng minh truy ch ng). th có t t c m i c nh hi n di n gi a m i c p nh c g i là th y (complete graphs). 6
Thu t ng (tt.) th th a; Các th v i s c nh t ng i ít c g i là th dày. các th v i ch m t s ít c nh m t i c g i là th mô t cho n gi là nh ng th vô h ng Các (undirected graphs). Trong các th có tr ng s (weighted graphs), nh ng giá tr s (tr ng s ) c g n vào m i c nh di n t thí d kho ng cách hay chi phí. Trong th có h ng (directed graphs) các c nh là “m t chi u”: m t c nh i t x sang y ch không ph i i t y sang x. c g i là các m ng Các th có h ng, có tr ng s còn (networks). 7
Cách bi u di n th Ta ph i ánh x các tên nh thành nh ng s nguyên trong t m tr gi a 1 và V. Gi s có t n t i hai hàm: - hàm index: chuy n i t tên nh thành s nguyên - hàm name: chuy n i s nguyên thành tên nh. Có hai cách bi u di n th : - dùng ma tr n k c n - dùng t p danh sách k c n 8
Cách bi u di n ma tr n k c n A B C D EFG H IJK LM M t ma tr n V A1 1 1 0 01 1 0 000 00 hàng V c t ch a B1 1 0 0 00 0 0 0 00 00 các giá tr Boolean C1 0 1 0 00 0 0 0 00 00 mà a[x, y] là true if D0 0 0 1 11 0 0 0 00 00 E0 0 0 1 11 1 0 0 00 00 n ut nt im t F1 0 0 1 11 0 0 000 00 nh x n c nh t G1 0 0 0 101 0 000 00 nh y và false n u H0 0 0 0 000 1 100 00 ng c l i. I0 0 0 0 000 1 100 00 J0 0 0 0 0 00 0 0 11 11 Hình 4.1b: Ma tr n k K0 0 0 0 00 0 0 0 11 00 c nc a th hình L0 0 0 0 00 0 0 0 10 11 4.1a M0 0 0 0 00 0 0 0 10 11 9
Ghi chú v cách bi u di n ma tr n k c n M i c nh t ng ng v i 2 bit trong ma tr n: m i c nh n i gi a x và y c bi u di n b ng giá tr true t i c a[x, y] và a[y, x]. ti n l i gi nh r ng có t n t i m t c nh n i m i nh v chính nó. th là d y. L i bi u di n này ch thích h p khi các 10
Gi i thu t program adjmatrix (input, output); const maxV = 50; var j, x, y, V, E: integer; a: array[1..maxV, 1..maxV] of boolean; begin readln (V, E); for x: = 1 to V do /*initialize the matrix */ for y: = 1 to V do a[x, y]: = false; for x: = 1 to V do a[x, y]: = true; for j: = 1 to E do begin readln (v1, v2); x := index(v1); y := index(v2); a[x, y] := true; a[y, x] := true end; end. 11
Cách bi u di n b ng t p danh sách k c n Trong cách bi u di n này, m i nh mà n i t i m t c k t thành m t danh sách k c n nh (adjacency-list ) cho nh ó. program adjlist (input, output); const maxV = 100; type link = node node = record v: integer; next: link end; var j, x, y, V, E: integer; t, x: link; adj: array[1..maxV] of link; 12
begin readln(V, E); new(z); z.next: = z; for j: = 1 to V do adj[j]: = z; for j: 1 to E do begin readln(v1, v2); x: = index(v1); y: = index(v2); new(t); t.v: = x; t.next: = adj[y]; adj[y]: = t; /* insert x to the first element of y’s adjacency list */ new(t); t.v = y; t.next: = adj[x]; adj[x]:= t; /* insert y to the first element of x’s adjacency list */ end; end. 13
a bc d e f g h i j k l m f a a f g a e i h k j j j c e f e a l m l b d d m g Hình 4.1c: Bi u di n b ng t p danh sách k c n c a th hình 4.1 14
Các ph ng pháp duy t th Duy t hay tìm ki m trên th : vi ng m i nh/nút trong th m t cách có h th ng. Có hai cách chính duy t th : - duy t theo chi u sâu tr c (depth-first-search ) - duy t theo chi u r ng tr c (breadth-first-search). 15
Duy t theo chi u sâu tr c – gi i thu t quy procedure dfs; procedure visit(n:vertex); begin add n to the ready stack; while the ready stack is not empty do get a vertex from the stack, process it, and add any neighbor vertex that has not been processed to the stack. if a vertex has already appeared in the stack, there is no need to push it to the stack, but it is moved to the top of the stack. end; begin Initialize status; for each vertex, say n, in the graph do if the status of n is “not yet visited” then visit(n) end; 16
Tìm ki m theo chi u sâu tr c – bi u di n danh sách k c n procedure list-dfs; var id, k: integer; val: array[1..maxV] of integer; procedure visit (k: integer); var t: link; begin id: = id + 1; val[k]: = id; /* change the status of k to “visited” */ t: = adj[k]; / * find the neighbors of the vertex k */ while t z do begin if val[t .v] = 0 then visit(t.v); t: = t.next end end; 17
begin id: = 0; for k: = 1 to V do val[k]: = 0; /initialize the status of all vetices */ for k: = 1 to V do if val[k] = 0 then visit(k) end; Ghi chú: M ng val[1..V] ch a tr ng thái c a các nh. val[k] = 0 n u nh k ch a h c vi ng (“not yet visited”), val[k] 0 n u nh k ã c vi ng. val[k]: = j ngh a là nh jth mà c vi ng trong quá trình duy t là nh k. 18
A A A A E F F F A A A A G G G G E E E E F F F F A A A A G G G G D E D E D E D E F F F F A A A A C B B G C G C G C G D E D E D E D E F F F F 19 Hình 4.2 Duy t theo chi u sâu tr c
Nh v y k t qu c a gi i thu t duy t DFS trên th cho hình 4.1a v i t p danh sách k c n cho hình 4.1c là AFEGDCG L u ý: th t c a các nh trong các danh sách k c n có nh h ng n th t duy t c a các nh khi áp d ng DFS. 20