Khoa học máy tính - Đồ thị

Trong toán học và tin học, đồ thị là đối tượng nghiên cứu cơ bản của lý thuyết đồ thị. Một cách không chính thức, đồ thị là một tập các đối tượng gọi là đỉnh nối với nhau bởi các cạnh. Thông thường, đồ thị được vẽ dưới dạng một tập các điểm (đỉnh, nút) nối với nhau bởi các đoạn thẳng (cạnh). Tùy theo ứng dụng mà một số cạnh có thể có hướng.
Nội dung trích xuất từ tài liệu:
Khoa học máy tính - Đồ thị ð th (Graph) Nguy n Phương TháiB môn Khoa H c Máy Tính – Khoa CNTT Trư ng ð i h c Công ngh - ðHQGHN Email: thainp@vnu.edu.vn ð 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 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 tgiá 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 ma tr n 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) 0 1 2 3 4 0 1 1 0 0 0 0 0 1 0 1 1 0 0 0 1 1 2 1 0 0 0 0 3 0 0 0 1 0 4 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 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 http://www.cs.princeton.edu/~wayne/cs423/lectures.html ði qua ñ th theo chi u r ng (Breadth first search)//ði qua ñ th theo b r ng xu t phát t vBreadthFirstSearch (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) if ( u chưa ñư c thăm) { (7) (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 ngBreadthFirstSearch_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 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ăm DepthFirstSearch (u) }}Xem ví d http://www.cs.princeton.edu/~wayne/cs423/lectures.html ði qua ñ th theo chi u sâu (Depth first search)// ði qua ñ th G=(V, E) theo chi u sâuDepthFirstSearch_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);}