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

Chia sẻ: Nguyen Van Dai | Ngày: | Loại File: PDF | Số trang:18

Thêm vào BST

Báo xấu

117
lượt xem 14
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Khoa học máy tính - Đồ thị

ð th (Graph) Nguy n Phương Thái B 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 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 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 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) 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 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 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â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); }