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.
Nội dung trích xuất từ tài liệu:
Bài giảng Đồ thị (Graph 2)th(Graph 2)Lê S VinhB môn Khoa H c Máy Tính – Khoa CNTTi H c Công Ngh - HQGHNEmail: vinhbio@gmail.comĐ th (graph)• G = (V, E)– V: T p nh– E = { (u,v) | u, v ∈ V}: T p c nhVí 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 mi qua th theo chi u r ng(Breadth first search)•i qua t t c cácnh c ath , m inh ú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 pt c quá trình thăm các nh theo nguyên t c: nh nào ư c thăm trư cthì các nh li n k v i nh ó s ư c thăm trư c• Xem ví dhttp://www.cs.princeton.edu/~wayne/cs423/lectures.htmli qua th theo chi u sâu(Depth first search)// i qua th theo chi u sâu xu t phát t vDepthFirstSearch (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ămDepthFirstSearch (u)}}Xem ví dhttp://www.cs.princeton.edu/~wayne/cs423/lectures.htmlS p x p topoChoth 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 v.GABCFED