Bài giảng Độ phức tạp thuật toán - Bài 8: Đồ thị (Graph) - Nguyễn Phương Thái

Nội dung text: Bài giảng Độ phức tạp thuật toán - Bài 8: Đồ thị (Graph) - Nguyễn Phương Thái

1. ð th (Graph) Nguyn Phương Thỏi B mụn Khoa Hc Mỏy Tớnh – Khoa CNTT Trưng ði hc Cụng ngh ðHQGHN Email: thainp@vnu.edu.vn
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, , n1} • Biu din bng ma trn lin k A – A[u][v] = 1 nu cú cung (u,v) – A[u][v] = 0 nu khụng cú cung (u,v) 0 1 2 3 4 0 0 1 1 0 0 1 0 0 1 0 1 2 0 0 0 1 1 3 1 0 0 0 0 4 0 0 0 1 0
10. Biu din ủ th G = (V, E); V = {0, 1, , n1} • Biu din bng danh sỏch k
11. ð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
12. ð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. }
13. ð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); }
14. ð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
15. ði qua ủ th theo chiu sõu (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); }