Bài giảng Lý thuyết đồ thị: Chương 2 - Tôn Quang Toại

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:38

Thêm vào BST

Báo xấu

7
lượt xem 3
download

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

Bài giảng Lý thuyết đồ thị: Chương 2 Biểu diễn đồ thị trên máy tính, cung cấp cho người đọc những kiến thức như: Biểu diễn đồ thị bằng ma trận kề, ma trận số; Biểu diễn đồ thị bằng Danh sách kề; Biểu diễn đồ thị bằng danh sách cạnh. Mời các bạn cùng tham khảo!

Chủ đề:

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

Lưu

Nội dung Text: Bài giảng Lý thuyết đồ thị: Chương 2 - Tôn Quang Toại

CHƯƠNG 2 BIỂU DIỄN ĐỒ THỊ TRÊN MÁY TÍNH Tôn Quang Toại Khoa CNTT, Đại học Ngoại ngữ ‐ Tin học TP.HCM
Nội dung Biểu diễn đồ thị bằng Ma trận kề, ma trận số Biểu diễn đồ thị bằng Danh sách kề Biểu diễn đồ thị bằng Danh sách cạnh
BIỂU DIỄN ĐỒ THỊ BẰNG MA TRẬN KỀ, MA TRẬN TRỌNG SỐ
Ma trận kề Đồ thị G=(V, E) có n đỉnh ( ) và m cạnh. Ma trận kề (adjacency matrix) của G là một mảng 2 chiều , trong đó cho biết G chứa những cạnh (i,j) hay không 1 𝑛ế𝑢 𝑐ạ𝑛ℎ 𝑖, 𝑗 ∈ 𝐸 𝑣 𝑖, 𝑗 0 𝑛ế𝑢 𝑐ạ𝑛ℎ 𝑖, 𝑗 ∉ 𝐸
Ma trận kề Ví dụ: Graph vô hướng 2 4 0 5 1 3 0 1 2 3 4 5 0 1 2 v = 3 4 5
Ma trận kề Ví dụ: Graph có hướng 2 4 0 5 1 3 0 1 2 3 4 5 0 1 2 v = 3 4 5
Ma trận kề Cấu trúc dữ liệu int[,] v; int n; Cấu trúc file dữ liệu của ma trận kề Graph.INP Số đỉnh 6 0 1 1 0 0 0 1 0 1 1 1 0 1 1 0 0 1 0 Ma trận kề 0 1 0 0 1 1 0 1 1 1 0 1 0 0 0 1 1 0
Ma trận kề Một số tính chất của ma trận kề Ma trận kề của đồ thị vô hướng là ma trận đối xứng: Ngược lại, ma trận đối xứng (0,1) bậc n sẽ tương ứng với đồ thị vô hướng n đỉnh Nếu đồ thị vô hướng: Số lượng số 1 trên dòng thứ i = Số lượng số 1 trên cột thứ i = deg(i) Nếu đồ thị có hướng: • Số lượng số 1 trên dòng i = tổng bậc ra của đỉnh i = deg+(i) • Số lượng số 1 trên cột i = tổng bậc vào của đỉnh i = deg ‐(i)
Ma trận kề Một số thao tác cơ bản trên cấu trúc Graph Kiểm tra có 1 cạnh nối đỉnh u đến đỉnh v không Xét các đỉnh kề với đỉnh u cho trước Thêm 1 cạnh nối đỉnh u đến đỉnh v nếu chưa có cạnh đó Xóa cạnh nối đỉnh u đến đỉnh v nếu có cạnh đó Xóa cạnh nối đỉnh u đến đỉnh v nếu có cạnh đó nhưng cho phép phục hồi lại sau này Xóa các cạnh kề với đỉnh u và xóa cả đỉnh u
Ma trận trọng số Đồ thị có trọng số: Mỗi cạnh e=(u,v) của đồ thị được gán với một con số w(u, v) gọi là trọng số của cạnh e. Trong trường hợp đồ thị có trọng số, thay vì dùng ma trận kề, chúng ta biểu diễn đồ thị bằng ma trận trọng số như sau 𝑤 𝑖, 𝑗 𝑛ế𝑢 𝑐ạ𝑛ℎ 𝑖, 𝑗 ∈ 𝐸 𝑣 𝑖, 𝑗 0 𝑛ế𝑢 𝑐ạ𝑛ℎ 𝑖, 𝑗 ∉ 𝐸
Ma trận trọng số 2 6 4 Ví dụ: 3 3 4 5 0 1 3 9 5 2 1 3 0 1 2 3 4 5 0 1 2 v = 3 4 5
GIỚI THIỆU COLLECTION
Một số loại collection cơ bản Collection tuyến tính LinkedList Tuple Stack Queue Collection không tuyến tính SortedSet SortedDictionary
LinkedList LinkedList: LinkedList là một cấu trúc dữ liệu cho phép chúng ta thêm, xóa phần tử với thời gian O(1) Tạo LinkedList và thêm các phần tử vào list LinkedList list = new LinkedList(); list.AddLast(4); list.AddLast(7); list.AddLast(3);
LinkedList Truy cập các phần tử trong LinkedList foreach (int x in list) Console.Write(x + " "); for (LinkedListNode node = list.First; node!=null; node=node.Next) Console.Write(node.Value + " ");
LinkedList Properties First Last Count Methods AddLast() AddFirst() Find()
Tuple Tuple: Tuple là một cấu trúc dữ liệu có một số phần tử tuần tự Tạo tuple chứa 2 số nguyên Tuple tuple; tuple= new Tuple(2,3); Console.Write(tuple.Item1 + " " + tuple.Item2);
Stack Stack: Stack là cấu trúc dữ liệu cung cấp 2 phép toán có thời gian chạy O(1): Thêm phần tử vào đầu (top) stack Xóa phần tử ở đầu stack Stack s = new Stack(); s.Push(5); s.Push(7); Console.Write(s.Peek()); s.Pop(); Console.Write(s.Peek());
Stack Property Count Methods Push() Pop() Peek()
Queue Queue: Queue là cấu trúc dữ liệu cung cấp 2 phép toán có thời gian chạy O(1): Thêm phần tử vào cuối queue Xóa phần tử đầu tiên trong queue Queue q = new Queue(); q.Enqueue(5); q.Enqueue(7); Console.Write(q.Peek()); q.Dequeue(); Console.Write(q.Peek());