Đồ thị - 1

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

Thêm vào BST

Báo xấu

111
lượt xem 12
download

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

Tham khảo tài liệu 'đồ thị - 1', khoa học tự nhiên, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả

Chủ đề:

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

Lưu

Nội dung Text: Đồ thị - 1

ð th (Graph) 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
Đ th (graph) • G = (V, E) – V: T p ñ nh – E = { (u,v) | u, v ∈ V}: T p c nh Ví d : Bi u di n b n ñ ñư ng ñi trong thành ph b ng ñ th G = (V, E) – V: T p h p các ñi m trong thành ph – E: T p h p các ñư ng ñi trong thành ph , m i ñư ng ñi n i hai ñi m
ði qua ñ th theo chi u r ng (Breadth first search) • ði qua t t c các ñ nh c a ñ th , m i ñ nh ñúng m t l n • B t ñ u xu t phát t m t ñ nh s, l n lư t thăm các ñ nh li n k v i s. Ti p t c quá trình thăm các ñ nh theo nguyên t c: ð nh nào ñư c thăm trư c thì các ñ nh li n k v i ñ nh ñó s ñư c thăm trư c • Xem ví d http://www.cs.princeton.edu/~wayne/cs423/lectures.html
ði qua ñ th theo chi u sâu (Depth first search) //ði qua ñ th theo chi u sâu xu t phát t v DepthFirstSearch (v) { for (m i ñ nh u k v i v) if (u chưa ñư c thăm) { thăm u và ñánh d u u ñã ñư c thăm DepthFirstSearch (u) } } Xem ví d http://www.cs.princeton.edu/~wayne/cs423/lectures.html
S p x p topo Cho ñ th có hư ng nhưng không có chu trình G = (V, E) (Directed acylic graph / DAG) S p x p các ñ nh c a ñ th G thành m t danh sách sao cho n u có cung (u,v) ∈ E, thì đ nh u ph i đ ng trư c đ nh v. GABCFED
S p x p topo TopoSort (u) { ðánh d u u ñã thăm; for (m i ñ nh v k u) if ( v chưa thăm) TopoSort(v); Xen u vào ñ u danh sách T; } //S p x p các ñ nh c a ñ th ñ nh hư ng //không có chu trình G =(V,E) thành danh sách topo. TopoSortGraph(G) { for (m i ñ nh u ∈ V) ðánh d u u chưa ñư c thăm; Kh i t o danh sách topo T r ng; for (m i ñ nh u ∈ V) if (u chưa thăm) TopoSort (u); }
ðư ng ñi gi a hai ñi m Cho ñ th G = (V, E) Gi a hai ñ nh (x0, xk) có ñư ng ñi, n u t n t i (x1,…,xk-1 ) th a mãn (xi, xi+1) ∈ E, ∀i = 0…(k-1)
ð th liên thông (Connected graph) Cho ñ th G = (V, E), G ñư c g i là liên thông n u t n t i ñư ng ñi gi a hai ñ nh b t kì c a ñ th
Tìm t t c các thành ph n liên thông Cho ñ th G = (V, E), tìm t t c các thành ph n liên thông c a ñ th . ð nh i c a ñ th ñư c gán nhãn ci cho bi t thu c mi n liên thông ci.
Tìm các thành ph n liên thông //ði qua ñ th theo b r ng xu t phát t v FindConnectedComponent (v, ci) { (1) Kh i t o hàng ñ i Q r ng; (2) Xen v vào hàng ñ i Q; (3) ðánh d u ñ nh v ñã ñư c thăm, và gán nhãn v b ng ci (4) while (hàng ñ i Q không r ng) { (5) L y ñ nh w ñ u hàng ñ i Q; (6) for (m i ñ nh u k w) (7) if ( u chưa ñư c thăm) { (8) Xen u vào ñuôi hàng ñ i Q; (9) ðánh d u u ñã ñư c thăm, và gán nhãn u b ng ci } (10) Lo i w ra kh i hàng ñ i Q } // h t vòng l p while. }
Tìm các thành ph n liên thông // Tìm các thành ph n liên thông c a ñ th G=(V, E) FindAllConnectedComponent (G) { (10) for (m i v ∈V) (11) ðánh d u v chưa ñư c thăm; (12) ci = 0; (13) for (m i v ∈V) (14) if (v chưa ñư c thăm) { (15) FindConnectedComponent(v, ci); (16) ci = ci + 1 } }
ðư ng ñi ng n nh t Cho ñ th G=(V, E), c nh (u, v) ∈ E có ñ dài weight (u,v) > 0. Tìm ñư ng ñi ng n nh t t ñ nh s ñ n ñ nh e Tư tư ng thu t toán Dijkstra (thu t toán gán nhãn) dist[v] = Kho ng cách ñư ng ñi ng n nh t t s ñ n v pre[v] = u: ð nh li n phía trư c trên ñư ng ñi ng n nh t t s ñ n v Gán nhãn (s a nhãn): N u dist[u] + weight (u, v) < dist [v] thì dist [v] = dist[u] + weight (u, v) pre[v] = u s→…→u→v
Thu t toán Dijkstra Known = {t p h p các ñ nh ñã xác ñ nh ñư c ñư ng ñi ng n nh t t s ñ n} Unknown = {t p h p các ñ nh chưa xác ñ nh ñư c ñư ng ñi ng n nh t t s ñ n} Ti n hành quá trình l p, t i bư c i tìm ñ nh u ∈ unknown có kho ng cách nh nh t. if u = e then k t thúc else { known = known ∪ {u} unknown = unknown – {u} Dùng u ñ s a nhãn cho các ñ nh thu c t p unknown ti n hành bư c th (i + 1) }
Dijkstra Algorithm { Known = {s}; Unknown = {E} – {s} for v ∈ unknown { dist[v] = weight [s, v]; pre[v] = s; } u = s; // at the first step while (u != e ){ ch n u sao cho dist[u] = min {dist[x] | x ∈ unknown} Known = Known ∪ {u} Unknown = Unknown – {u} for v ∈ Unknown if dist[u] + weight [u, v] < dist[v] { //s a nhãn cho v t u dist[v] = dist[u] + weight[u,v]; pre[v] = u; } } path = {e} while (e != s) { e = pre[e] path = {e} ∪ path } }