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

th<br /> (Graph 2)<br /> Lê S Vinh<br /> B môn Khoa H c Máy Tính – Khoa CNTT<br /> i H c Công Ngh - HQGHN<br /> Email: vinhbio@gmail.com<br /> <br /> Đ th (graph)<br /> • G = (V, E)<br /> – V: T p nh<br /> – E = { (u,v) | u, v ∈ V}: T p c nh<br /> <br /> Ví d : Bi u di n b n<br /> ư ng i trong thành ph b ng th G = (V, E)<br /> – V: T p h p các i m trong thành ph<br /> – E: T p h p các ư ng i trong thành ph , m i ư ng i n i hai i m<br /> <br /> i qua th theo chi u r ng<br /> (Breadth first search)<br /> •<br /> <br /> i qua t t c các<br /> <br /> nh c a<br /> <br /> th , m i<br /> <br /> nh úng m t l n<br /> <br /> • 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<br /> t c quá trình thăm các nh theo nguyên t c: nh nào ư c thăm trư c<br /> thì các nh li n k v i nh ó s ư c thăm trư c<br /> • Xem ví d<br /> http://www.cs.princeton.edu/~wayne/cs423/lectures.html<br /> <br /> i qua th theo chi u sâu<br /> (Depth first search)<br /> // i qua th theo chi u sâu xu t phát t v<br /> DepthFirstSearch (v) {<br /> for (m i nh u k v i v)<br /> if (u chưa ư c thăm) {<br /> thăm u và ánh d u u ã ư c thăm<br /> DepthFirstSearch (u)<br /> }<br /> }<br /> Xem ví d<br /> http://www.cs.princeton.edu/~wayne/cs423/lectures.html<br /> <br /> S p x p topo<br /> Cho<br /> <br /> th có hư ng nhưng không có chu trình G = (V, E)<br /> (Directed acylic graph / DAG)<br /> <br /> S p x p các nh c a th G thành m t danh sách sao cho n u có cung<br /> (u,v) ∈ E, thì đ nh u ph i đ ng trư c đ nh v.<br /> <br /> GABCFED<br /> <br />