Một số vấn ñề khác trong ñồ thị
(Tự ñọc)(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:
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++)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
0
1
3
4
2
5

T = T ∪ {(u,v};
}
}