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

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

Báo xấu

144
lượt xem 16
download

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ị

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
Cây tìm ki m nh phân cân b ng AVL (G.M. Adelson-Velsky and E.M. Landis)
ðư 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]
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
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}; } }
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)