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.
, trong đó
cho biết G
Ma trận kề (adjacency matrix) của G là một mảng 2 chiều chứa những cạnh (i,j) hay không
𝑣 𝑖, 𝑗 (cid:3404) (cid:4682)
1 𝑛ế𝑢 𝑐ạ𝑛ℎ (cid:4666)𝑖, 𝑗(cid:4667) ∈ 𝐸 0 𝑛ế𝑢 𝑐ạ𝑛ℎ (cid:4666)𝑖, 𝑗(cid:4667) ∉ 𝐸
Ma trận kề
Ví dụ: Graph vô hướng
2
4
5
0
3
1
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
5
0
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ề
Số đỉnh
Ma trận kề
Graph.INP 6 0 1 1 0 0 0 1 0 1 1 1 0 1 1 0 0 1 0 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
𝑣 𝑖, 𝑗 (cid:3404) (cid:4682)
𝑤(cid:4666)𝑖, 𝑗(cid:4667) 𝑛ế𝑢 𝑐ạ𝑛ℎ (cid:4666)𝑖, 𝑗(cid:4667) ∈ 𝐸 𝑛ế𝑢 𝑐ạ𝑛ℎ (cid:4666)𝑖, 𝑗(cid:4667) ∉ 𝐸
0
Ma trận trọng số
4
2
6
Ví dụ:
3
3
4
5
0
1
3
9
5
2
3
1
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());
Queue
Properties Count
Methods
Enqueue() Dequeue() Peek()
SortedSet
SortedSet: SortedSet là cấu trúc dữ liệu để chứa tập hợp các phần tử. Các phép toán cơ bản trên tập hợp là: Thêm, Xóa, Tìm kiếm với thời gian
SortedSet s = new SortedSet();
s.Add(2);
s.Add(2);
s.Add(3);
s.Add(1);
Console.Write(s.Count);
foreach (int x in s)
Console.Write(x + " ");
SortedSet
Properties Count Max Min
Methods Add() Remove() Contains()
SortedDictionary
SortedDictionary: SortedDictionary là mảng tổng quát gồm các cặp key‐value
Key của mảng thông thường: 0, 1, 2, …, n‐1 Key của dictionary là bất kỳ kiểu nào Thời gian truy cập phần tử là
SortedDictionary d = new SortedDictionary();
d["a"] = 4;
d["b"] = 8;
d["c"] = 2;
foreach (KeyValuePair
Console.Write(x.Value);
SortedDictionary
Properties Count Values Keys
Methods Add() Remove() ContainsValue(), ContainsKey()
BIỂU DIỄN ĐỒ THỊ BẰNG DANH SÁCH KỀ
Danh sách kề
Trong biểu diễn danh sách kề (Adjacency list) của đồ thị G = (V,E), mỗi đỉnh v của đồ thị chúng ta lưu trữ danh sách các đỉnh kề với v.
Nếu đồ thị không có trọng số
LinkedList[] v;
Danh sách kề
LinkedList
2
3
0
v[1] = new LinkedList
1
v[2] = new LinkedList
v[3] = new LinkedList
Danh sách kề
Nếu đồ thị có trọng số
LinkedList>[] v;
2
1
3
4
8 5
0
7
1
Danh sách kề
LinkedList
v[1] = new LinkedList
v[2] = new LinkedList
v[3] = new LinkedList
Danh sách kề
Cấu trúc file dữ liệu của danh sách kề
Graph.INP
2
4
Số đỉnh
0
3
Danh sách các đỉnh kề của các đỉnh 0, 1, …, 4
1
5 1 2 0 2 4 0 1 4 4 1 2 3
BIỂU DIỄN ĐỒ THỊ BẰNG DANH SÁCH CẠNH
Danh sách cạnh
Danh sách cạnh (edge list): chứa tất cả các cạnh của đồ thị theo một trật tự.
Danh sách cạnh rất tiện dụng khi thuật toán:
Xử lý tất cả các cạnh của đồ thị Không cần tìm các cạnh của một đỉnh
LinkedList> e
Danh sách cạnh
2
4
0
1
3
e.AddLast(new Tuple
Danh sách cạnh
Cấu trúc file dữ liệu của danh sách cạnh
Graph.INP
Số cạnh Số đỉnh
Danh sách cạnh
6 9 0 1 0 2 1 2 1 3 1 4 2 4 3 4 3 5 4 5
Danh sách cạnh
Nếu đồ thị có trọng số
LinkedList> e;
2
1
3
4
8 5
0
7
1
Chọn cách biểu diễn đồ thị trên máy tính
Chọn lựa cách biểu diễn đồ thị: Phụ thuộc vào
Thuật toán xử lý trên đồ thị Số lượng đỉnh
Chú ý:
Có thể kết hợp một số cách biểu diễn với nhau Có thể chọn các cấu trúc dữ liệu khác để biểu diễn đồ thị
Tóm tắt chương 2
Có 3 cách thông thường để biểu diễn đồ thị
Ma trận kề, Ma trận trọng số
Danh sách kề
Danh sách cạnh
