Một số vấn đề khác trong đồ thị

Chia sẻ: Le Quang Duan Duan | Ngày: | Loại File: PDF | Số trang:6

0
98
lượt xem
15
download

Một số vấn đề khác trong đồ thị

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

Tài liệu tham khảo một số vấn đề khác trong đồ thị - môn Khoa học máy tính

Chủ đề:
Lưu

Nội dung Text: Một số vấn đề khác trong đồ thị

  1. M t s v n ñ khác trong ñ th (T ñ c) Lê S Vinh B môn Khoa H c Máy Tính – Khoa CNTT ð i H c Công Ngh - ðHQGHN Email: vinhioi@yahoo.com
  2. Cây tìm ki m nh phân cân b ng AVL (G.M. Adelson-Velsky and E.M. Landis)
  3. ðư ng ñi ng n nh t gi a m i c p ñ nh Input: ð th G = (V, E) Output: Ma tr n Dist[u,v] là ñư ng ñi ng n nh t gi a hai ñ nh u và v Thu t toán Floyd: for ( u = 0 ; u < n ; u++) for ( v = 0 ; v < n ; v++) Dist[u][v] = weight[u][v]; for ( k = 0 ; k < n ; k++) for ( u = 0 ; u < n ; u++) for ( v = 0 ; v < n ; v++) if (Dist[u][k] + Dist[k][v] < Dist[u][v] ) Dist[u][v] = Dist[u][k] + Dist[k][v]
  4. Cây bao trùm ng n nh t (minimum spanning tree) • ð th không hư ng G = (V, E), cây bao trùm T là ñ th con c a G, liên thông, không chu trình và n i t t c các ñ nh V c a G • Cây bao trùm ng n nh t là cây có t ng ñ dài các c nh ng n nh t 4 0 3 1 4 0 4 9 3 1 6 3 5 3 5 7 6 8 8 5 5 1 2 2 2 1 2
  5. Cây bao trùm ng n nh t (minimum spanning tree) Prim(G,T) //Xây d ng cây bao trùm ng n nh t T c a ñ th G { U = {s}; //Kh i t o t p U ch chưa m t ñ nh s T = ∅; // Kh i t o t p c nh T r ng. while ( U ≠ V ) { ch n (u,v) là c nh ng n nh t v i u ∈ U và v ∈ V - U; U = U ∪ {v}; T = T ∪ {(u,v}; } }
  6. 0 4 4 9 4 3 1 0 4 9 3 1 7 3 6 5 8 8 7 3 6 5 5 8 8 1 2 2 5 (a) 1 2 2 4 (b) 0 4 9 3 1 0 4 4 9 3 1 7 3 6 5 8 8 7 3 6 5 5 8 8 1 2 5 2 1 2 (c) 2 (d) 4 0 4 9 3 1 0 4 4 9 3 1 7 3 6 5 7 3 6 5 8 8 8 8 5 5 1 2 2 1 2 2 (e) (f)

CÓ THỂ BẠN MUỐN DOWNLOAD

Đồng bộ tài khoản