tailieunhanh - Bài giảng Đồ thị (Graph 2)

Bài giảng Đồ thị (Graph 2) giới thiệu tới các bạn về đi qua đồ thị theo chiều rộng, đi qua đồ thị theo chiều sâu, sắp xếp topo, đường đi giữa hai điểm, đồ thị liên thông (Connected graph), tìm tất cả các thành phần liên thông. | th (Graph 2) Lê S Vinh B môn Khoa H c Máy Tính – Khoa CNTT i H c Công Ngh - HQGHN Email: vinhbio@ Đ 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 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 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 .