Đồ thị - 2

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

Thêm vào BST

Báo xấu

129
lượt xem 15
download

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

Tài liệu tham khảo về đồ 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: Đồ thị - 2

ð 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
ð th có hư ng và không có hư ng (directed and undirected graph) G = (V, E) là ñ th không có hư ng n u (u, v) ∈ E thì (v, u) ∈ E
ð th có tr ng s và không có tr ng s (weighted and unweighted graph) G = (V, E) là ñ th có tr ng s n u m i c nh (u, v) ∈ E ñư c gán m t giá tr
ð th có chu trình và không chu trình (cyclic and acyclic graph)
ð th không có nhãn và ñ th có nhãn (unlabled and labled graph)
Friend graph
B c c a ñ nh (vertex degree)
Bi u di n ñ th G = (V, E); V = {0, 1,…, n-1} • Bi u di n b ng danh sách li n k A – A[u][v] = 1 n u có cung (u,v) – A[u][v] = 0 n u không có cung (u,v)
Bi u di n ñ th G = (V, E); V = {0, 1,…, n-1} • Bi u di n b ng danh sách k
ði qua ñ th • ði qua t t c các ñ nh, m i ñ nh m t l n 0, 1, 2, 3, 4 • ði qua t t c các c nh, m i c nh m t l n (0,1), (0, 2), (1, 2), (1, 4), (2, 3), (2, 4), (4, 3), (3, 0)
ð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 r ng (Breadth first search) //ði qua ñ th theo b r ng xu t phát t v BreadthFirstSearch (v) { (1) Kh i t o hàng ñ i Q r ng; (3) Xen v vào hàng ñ i Q; (2) ðánh d u ñ nh v ñã ñư c thăm; (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; } (10) Lo i w ra kh i hàng ñ i Q } // h t vòng l p while. }
ði qua ñ th theo chi u r ng (Breadth first search) // ði qua ñ th G=(V, E) theo b r ng BreadthFirstSearch_traversal (G) { (10) for (m i v ∈V) (11) ðánh d u v chưa ñư c thăm; (12) for (m i v ∈V) (13) if (v chưa ñư c thăm) (14) BreadthFirstSearch(v); }
ð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
ði qua ñ th theo chi u r ng (Depth first search) // ði qua ñ th G=(V, E) theo chi u sâu DepthFirstSearch_traversal (G) { (10) for (m i v ∈V) (11) ðánh d u v chưa ñư c thăm; (12) for (m i v ∈V) (13) if (v chưa ñư c thăm) (14) DepthFirstSearch(v); }