Cấu trúc dữ liệu và giải thuật (Đỗ Tuấn Anh) - Chương 6. Đồ thị và một vài cấu trúc phi tuyến khác

Danh sách kề là một mảng A[0..n-1] các danh sách, với nlà số đỉnh của đồ thị.Chỉ số của mảng tương ứng với chỉ số của đỉnh.Mỗi danh sách A[i] lưu trữ các chỉ số của các đỉnh kề vớiđỉnh i.
Nội dung trích xuất từ tài liệu:
Cấu trúc dữ liệu và giải thuật (Đỗ Tuấn Anh) - Chương 6. Đồ thị và một vài cấu trúc phi tuyến khácCấu trúc dữ liệu và giải thuật Đỗ Tuấn Anh anhdt@it-hut.edu.vnNội dung Chương 1 – Thiết kế và phân tích (5 tiết) Chương 2 – Giải thuật đệ quy (10 tiết) Chương 3 – Mảng và danh sách (5 tiết) Chương 4 – Ngăn xếp và hàng đợi (10 tiết) Chương 5 – Cấu trúc cây (10 tiết) Chương 8 – Tìm kiếm (5 tiết) Chương 7 – Sắp xếp (10 tiết) Chương 6 – Đồ thị và một vài cấu trúc phi tuyến khác (5 tiết) Chương 9 – Sắp xếp và tìm kiếm ngoài (after)Chương 6 – Đồ thị và một vài cấu trúc phituyến khác1. Định nghĩa và khái niệm2. Biểu diễn đồ thị • Ma trận lân cận • Danh sách lân cận3. Phép duyệt đồ thị • Theo chiều sâu • Theo chiều rộng4. Ứng dụng • Bài toán bao đóng truyền ứng • Bài toán sắp xếp topo5. Giới thiệu về danh sách tổng quát, đa danh sách (not yet)1. Định nghĩa và khái niệm Đồ thị Một đồ thị G bao gồm một tập V(G) các đỉnh (nút) và một tập E(G) các cạnh (cung) là các cặp đỉnh.đỉnh a b c d cạnh e f g h i j k l 12 đỉnh V = { a, b, c, d, e, f, g, h, i, j, k, l } E = { (a, b), (a, e), (b, e), (b, f), (c, j), (c, g), (c, h), (d, h), (e, j), (g, k), (g, l), (g, h), (i, j) } 13 cạnhĐồ thị định hướngTrong đồ thị định hướng (digraph), các cạnh là những cặpcó thứ tự. TW 45 BOS NW 35 ORD DL 247 SFO JFK AA 903 DL 335 UA 877 AA 1387 0 12 MIA UA AA 49 AA 523 LAX DFW AA 411Ứng dụng của đồ thịĐồ thị mô tả các mối quan hệ Mạng Internet Mạng lưới đường giao thông Nguyên tử Sơ đồ cấu trúc điều khiển Mạng lưới xã hội George Paul Linda Ringo Yoko John Bề mặt địa lý (CAD) Mạch điện …Các loại đồ thị khácĐa đồ thị cho phép có thể có nhiều cạnh giữa 2 đỉnh. a c b d fGiả đồ thị là một đa đồ thị cho phép vòng lặp (là các cạnh từ một đỉnhđến chính nó). 2 1 3 5 6 4 Cạnh và Đỉnh bậc(w) = 1 w e2 u u và v gọi là lân cận của nhau hay kề nhau (adjacent)bậc(u) = 2 e1 v bậc vào(b) = 3 bậc ra(b) = 4 c đỉnh nguồn b a e đỉnh đích d Đường đi Một đường đi có độ dài k là một chuỗi các đỉnh v , v , …, v k mà 0 1 (vi , vi+1 ) với i = 0, 1, …, k – 1 là cạnh của G. b, c, d không phải đường đi a b c dĐường đi đơn:a, e, k, p, l, qm, h, d, c, g e f h g(không có đỉnh Không phải đường đi đơn:lặp lại) a, b, e, f, g, b, g, l m j k l p q n o Chu trình Một chu trình là một đường đi có đỉnh đầu và đỉnh cuối trùng nhau. Một chu trình đơn không có đỉnh trùng nhau trừ đỉnh đầu và đỉnh cuối. ...