Bài giảng Khoa học máy tính - Bài 7: Đồ thị (Graph) - Lê Sỹ Vinh

Nội dung text: Bài giảng Khoa học máy tính - Bài 7: Đồ thị (Graph) - Lê Sỹ Vinh

1. ð th (Graph) Lờ S Vinh B mụn Khoa Hc Mỏy Tớnh – Khoa CNTT ði Hc Cụng Ngh ðHQGHN Email: vinhioi@yahoo.com
2. Đ th (graph) • G = (V, E) – V: Tp ủnh – E = { (u,v) | u, v ∈ V}: Tp cnh Vớ d: Biu din bn ủ ủưng ủi trong thành ph bng ủ th G = (V, E) – V: Tp hp cỏc ủim trong thành ph – E: Tp hp cỏc ủưng ủi trong thành ph, mi ủưng ủi ni hai ủim
3. ð th cú hưng và khụng cú hưng (directed and undirected graph) G = (V, E) là ủ th khụng cú hưng nu (u, v) ∈ E thỡ (v, u) ∈ E
4. ð th cú trng s và khụng cú trng s (weighted and unweighted graph) G = (V, E) là ủ th cú trng s nu mi cnh (u, v) ∈ E ủưc gỏn mt giỏ tr
5. ð th cú chu trỡnh và khụng chu trỡnh (cyclic and acyclic graph)
6. ð th khụng cú nhón và ủ th cú nhón (unlabled and labled graph)
7. Friend graph
8. Bc ca ủnh (vertex degree)
9. Biu din ủ th G = (V, E); V = {0, 1, , n-1} • Biu din bng danh sỏch lin k A – A[u][v] = 1 nu cú cung (u,v) – A[u][v] = 0 nu khụng cú cung (u,v)
10. Biu din ủ th G = (V, E); V = {0, 1, , n-1} • Biu din bng danh sỏch k
11. ði qua ủ th • ði qua tt c cỏc ủnh, mi ủnh mt ln 0, 1, 2, 3, 4 • ði qua tt c cỏc cnh, mi cnh mt ln (0,1), (0, 2), (1, 2), (1, 4), (2, 3), (2, 4), (4, 3), (3, 0)
12. ði qua ủ th theo chiu rng (Breadth first search) • ði qua tt c cỏc ủnh ca ủ th, mi ủnh ủỳng mt ln • Bt ủu xut phỏt t mt ủnh s, ln lưt thăm cỏc ủnh lin k vi s. Tip tc quỏ trỡnh thăm cỏc ủnh theo nguyờn tc: ðnh nào ủưc thăm trưc thỡ cỏc ủnh lin k vi ủnh ủú s ủưc thăm trưc • Xem vớ d
13. ði qua ủ th theo chiu rng (Breadth first search) //ði qua ủ th theo b rng xut phỏt t v BreadthFirstSearch (v) { (1) Khi to hàng ủi Q rng; (3) Xen v vào hàng ủi Q; (2) ðỏnh du ủnh v ủó ủưc thăm; (4) while (hàng ủi Q khụng rng) { (5) Ly ủnh w ủu hàng ủi Q; (6) for (mi ủ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 du u ủó ủưc thăm; } (10) Loi w ra khi hàng ủi Q } // ht vũng lp while. }
14. ði qua ủ th theo chiu rng (Breadth first search) // ði qua ủ th G=( V, E) theo b rng BreadthFirstSearch_traversal (G) { (10) for (mi v ∈V) (11) ðỏnh du v chưa ủưc thăm; (12) for (mi v ∈V) (13) if ( v chưa ủưc thăm) (14) BreadthFirstSearch( v); }
15. ði qua ủ th theo chiu sõu (Depth first search) //ði qua ủ th theo chiu sõu xut phỏt t v DepthFirstSearch (v) { for (mi ủnh u k vi v) if ( u chưa ủưc thăm) { thăm u và ủỏnh du u ủó ủưc thăm DepthFirstSearch ( u) } } Xem vớ d
16. ði qua ủ th theo chiu rng (Depth first search) // ði qua ủ th G=( V, E) theo chiu sõu DepthFirstSearch_traversal (G) { (10) for (mi v ∈V) (11) ðỏnh du v chưa ủưc thăm; (12) for (mi v ∈V) (13) if ( v chưa ủưc thăm) (14) DepthFirstSearch( v); }