Bài giảng Cấu trúc dữ liệu: Chương 5 - TS. Trần Cao Đệ

Bài giảng Cấu trúc dữ liệu: Chương 5 - Đồ thị trình bày các kiểu dữ liệu trừu tượng đồ thị, biểu diễn đồ thị, các phép duyệt đồ thị,... Tham khảo nội dung bài giảng để hiểu rõ hơn về các nội dung trên.
Nội dung trích xuất từ tài liệu:
Bài giảng Cấu trúc dữ liệu: Chương 5 - TS. Trần Cao Đệ CHƯƠNG V:ĐỒ THỊ (GRAPH) TS. Trần Cao Đệ Năm 2007 ĐỒ THỊ„ Một đồ thị G=(V,E). V tập hợp các đỉnh (nút, điểm); E tập hợp các cung (cạnh) „ Cung nối giữa hai đỉnh (v,w), hai đỉnh này có thể trùng nhau. „ Hai đỉnh có cung nối nhau gọi là hai đỉnh kề „ Cung (v,w) có thứ tự thì ta có cung có thứ tự, ngược lại thì cung không có thứ tự.„ Đồ thị có hướng, vô hướng„ Đường đi (path) là một dãy tuần tự các đỉnh v1, v2,..., vn sao cho (vi,vi+1) là một cung trên đồ thị (i=1,...,n-1). Đường đi này là đường đi từ v1 đến vn và đi qua các đỉnh v2,...,vn-1. „ Đỉnh v1 còn gọi là đỉnh đầu, vn gọi là đỉnh cuối. Độ dài của đường đi này bằng (n-1). „ Trường hợp đặc biệt dãy chỉ có một đỉnh v thì ta coi đó là đường đi từ v đến chính nó có độ dài bằng không. „ đỉnh đầu và đỉnh cuối có thể trùng nhau. Một đường đi có đỉnh đầu và đỉnh cuối trùng nhau gọi là một chu trình (cycle). „ Một chu trình đơn là một đường đi đơn có đỉnh đầu và „ đỉnh cuối trùng nhau và có độ dài ít nhất là 1. Ví dụ trong hình thì 3, 2, 4, 3 tạo thành một chu trình có độ dài 3.„ Trong nhiều ứng dụng ta thường kết hợp các giá trị (value) hay nhãn (label) với các đỉnh và/hoặc các cạnh, lúc này ta nói đồ thị có nhãn.„ Đồ thị con của một đồ thị G=(V,E) là một đồ thị G=(V,E) trong đó: „ V’ V và „ E’ gồm tất cả các cạnh (v,w) E sao cho v,w V’. KIỂU DỮ LIỆU TRỪU TƯỢNG ĐỒ THỊ„ Các phép toán trên đồ thị „ Thông thường trong các giải thuật trên đồ thị: „ Đọc nhãn của đỉnh. For (mỗi đỉnh w kề với v) { „ Đọc nhãn của cạnh. thao tác nào đó trên w „ Thêm một đỉnh vào đồ } thị. „ Thêm một cạnh vào đồ „ Định nghĩa thêm các phép toán thị. sau đây: „ FIRST(v): trả về chỉ số của „ Xoá một đỉnh. đỉnh đầu tiên kề với v. hoặc „ Xoá một cạnh. Null „ Lần theo (navigate) các „ NEXT(v,i): trả về chỉ số của cung trên đồ thị để đi từ đỉnh nằm sau đỉnh có chỉ số i và kề với v. hoặc Null đỉnh này sang đỉnh khác. „ VERTEX(i): trả về đỉnh có chỉ số i. BIỂU DIỄN ĐỒ THỊ Ma trận kề„ Ta dùng một mảng hai chiều Anxn, kiểu boolean„ Giả sử các đỉnh được đánh số 1..n thì „ A[i,j] = true, nếu có đỉnh nối giữa đỉnh thứ i và đỉnh thứ j, „ ngược lại thì A[i,j] = false.„ Trong cài đặt bằng C, có thể phải thay A[i,j] bởi A[i-1,j- 1]Cài đặt các phép toán //trả ra đỉnh sau đỉnh I mà kề với v int NEXT(int v, int i) { int j;FIRST, NEXT và VERTEX như sau: for (j=i+1; j„ Trên đồ thị có nhãn thì ma trận kề có thể dùng để lưu trữ nhãn của các cung chẳng hạn cung giữa i và j có nhãn a thì A[i,j]=a.„ Nếu i,j không có cung nối thì A[i,j]=??? sẽ được lựa chọn tùy theo bài toánBiểu diễn bằng danh sách các đỉnh kề CÁC PHÉP DUYỆT ĐỒ THỊ„ Duyệt theo chiều sâu //đánh dấu chưa duyệt tất cả các đỉnh (depth-first search) for (v =1; v CÁC PHÉP DUYỆT ĐỒ THỊ (tt) F G A „ Thứ tự duyệt đồ thị theo chiều sâu: AGBCDFE. E D C B B F G Duyệt theo chiều sâu „ Thứ tự duyệt đồ thị theo chiều sâu là:A D ABFDCEG. C E CÁC PHÉP DUYỆT ĐỒ THỊ (tt)„ Duyệt theo chiều rộng (breadth-first search) „ Giả sử đồ thị G với các đỉnh ban đầu được đánh dấu là chưa duyệt (unvisited). „ Từ một đỉnh v nào đó ta bắt đầu duyệt : „ đánh dấu v đã được duyệt, „ kế đến là duyệt tất cả các đỉnh kề với v. „ Khi ta duyệt một đỉnh v rồi đến đỉnh w thì các đỉnh kề của v được duyệt trước các đỉnh kề của w„ Dùng một hàng để lưu trữ các nút theo thứ tự được duyệt để có thể duyệt các đỉnh kề với chúng. Duyệt bfs//đánh dấu chưa duyệt tất cả các đỉnh void bfs(vertex v) {// v [1..n]for (v = 1; v Ví dụ Bắt ...