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

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
Nội dung trích xuất từ tài liệu:
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 ngAVL (G.M. Adelson-Velsky and E.M. Landis) ðư ng ñi ng n nh t gi a m i c p ñ nhInput: ð th G = (V, E)Output: Ma tr n Dist[u,v] là ñư ng ñi ng n nh t gi a hai ñ nh u và vThu 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 17 3 6 5 8 8 7 3 6 5 5 8 81 2 2 5 (a) 1 2 2 4 (b)0 4 9 3 1 0 4 4 9 3 17 3 6 5 8 8 7 3 6 5 5 8 81 2 5 2 1 2 (c) 2 (d) 40 4 9 3 1 0 4 4 9 3 17 3 6 5 7 3 6 5 8 8 8 8 5 51 2 2 1 2 2 (e) ...