Cấu trúc dữ liệu và giải thuật 2008-2009 - Bài 7: Đồ thị

ðồ 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ụ ð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ụ ð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); }