» Khoa Học Tự Nhiên

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

Báo xấu

101
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ủ đề:

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

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)

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Giấy phép ICP số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2009-2015 TaiLieu.VN. All rights reserved. TaiLieu.VN hiển thị tốt nhất với trình duyệt Chrome, Firefox, Internet Explorer 8.