Tài liệu Luận văn cntt tối ưu hóa truy vấn tìm đường ngắn nhất trên đồ thị động quy mô lớn

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ PHẠM HẢI ĐĂNG TỐI ƯU HÓA TRUY VẤN TÌM ĐƯỜNG NGẮN NHẤT TRÊN ĐỒ THỊ ĐỘNG QUY MÔ LỚN LUẬN VĂN THẠC SĨ NGÀNH HỆ THỐNG THÔNG TIN Hà Nội – 2016 1 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ TRANG PHỤ BÌA PHẠM HẢI ĐĂNG TỐI ƯU HÓA TRUY VẤN TÌM ĐƯỜNG NGẮN NHẤT TRÊN ĐỒ THỊ ĐỘNG QUY MÔ LỚN Ngành: Hệ thống thông tin Chuyên ngành: Hệ thống thông tin Mã số: 60480104 LUẬN VĂN THẠC SĨ NGÀNH HỆ THỐNG THÔNG TIN NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS.TS. Nguyễn Ngọc Hóa Hà Nội – 2016 2 LỜI CẢM ƠN Để có thể hoàn thiện được luận văn thạc sỹ của mình, trước tiên, tôi xin bày tỏ lòng biết ơn sâu nhất tới thầy – PGS.TS. Nguyễn Ngọc Hóa (bộ môn Các hệ thống thông tin – trường Đại học Công nghệ – Đại học Quốc gia Hà Nội). Sự gần gũi, khích lệ và nhiệt tình hướng dẫn của thầy là nguồn động lực rất lớn đối với tôi trong suốt thời gian thực hiện luận văn. Tôi cũng xin được gửi lời cảm ơn chân thành nhất tới tất cả các thầy, cô trong bộ môn Các hệ thống thông tin, cũng như các thầy, cô trong khoa Công nghệ thông tin – trường Đại học Công nghệ – Đại học Quốc gia Hà Nội đã nhiệt tình giảng dạy, cung cấp cho chúng tôi những kiến thức, kinh nghiệm không chỉ trong học tập mà còn trong cuộc sống hàng ngày. Đồng thời tôi cũng xin được gửi lời cảm ơn đến cha mẹ, người thân trong gia đình, các bạn học viên, đồng nghiệp đã giúp đỡ, động viên, tạo điều kiện tốt nhất cho tôi trong suốt khóa học tại Trường Đại học Công nghệ – Đại học Quốc gia Hà Nội để tôi có thể hoàn thiện tốt luận văn thạc sỹ của mình. Hà Nội, tháng 11 năm 2016 Học viên Phạm Hải Đăng 3 LỜI CAM ĐOAN Tôi xin cam đoan luận văn tốt nghiệp “Tối ưu hóa truy vấn tìm đường ngắn nhất trên đồ thị động quy mô lớn” là công trình nghiên cứu thực sự của bản thân, được thực hiện trên cơ sở nghiên cứu lý thuyết, kiến thức chuyên ngành, nghiên cứu khảo sát tình hình thực tiễn và dưới sự hướng dẫn khoa học của PGS.TS. Nguyễn Ngọc Hóa. Các kết quả được viết chung với các tác giả khác đều được sự đồng ý của tác giả trước khi đưa vào luận văn. Những phần tham chiếu, trích dẫn trong luận văn đều được nêu rõ trong phần tài liệu tham khảo. Các số liệu, kết quả trình bày trong luận văn là hoàn toàn trung thực. Nếu sai tôi xin chịu hoàn toàn trách nhiệm và chịu mọi kỷ luật của khoa và nhà trường đề ra. Hà Nội, tháng 11 năm 2016 Học viên Phạm Hải Đăng 4 MỤC LỤC TRANG PHỤ BÌA ................................................................................................ 1 LỜI CẢM ƠN ....................................................................................................... 2 LỜI CAM ĐOAN ................................................................................................. 3 MỤC LỤC ............................................................................................................ 4 DANH MỤC CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮT ........................................... 6 DANH MỤC CÁC BẢNG ................................................................................... 7 DANH MỤC CÁC HÌNH VẼ .............................................................................. 8 Giới thiệu chung.................................................................................................... 9 Động lực nghiên cứu ......................................................................................... 9 Mục tiêu và nội dung chính của luận văn ......................................................... 9 Tổ chức luận văn ............................................................................................... 9 Chương 1: Cơ sở lý thuyết và các vấn đề liên quan ........................................... 10 1.1. Đồ thị ....................................................................................................... 10 1.1.1. Giới thiệu đồ thị ................................................................................ 13 1.1.2. Một số thuật ngữ cơ bản ................................................................... 14 1.1.3. Biểu diễn đồ thị ................................................................................. 15 1.1.4. Các thuật toán tìm kiếm trên đồ thị và ứng dụng .............................. 18 1.2. Bài toán tìm đường đi ngắn nhất .............................................................. 21 1.3. Tổng kết chương ...................................................................................... 27 Chương 2: Bài toán, cách tiếp cận và phương pháp giải quyết .......................... 28 2.1. Định nghĩa bài toán .................................................................................. 28 2.2. Các vấn đề liên quan ................................................................................ 29 2.3. Cách tiếp cận giải quyết bài toán ............................................................. 34 2.4. Cấu trúc dữ liệu phù hợp.......................................................................... 34 2.5. Tối ưu quá trình thêm và xóa cạnh của đồ thị.......................................... 37 2.5.1. Thêm mới một cạnh .......................................................................... 37 2.5.2. Xóa đi một cạnh ................................................................................ 39 2.6. Tối ưu quá trình xử lý truy vấn tìm đường ngắn nhất .............................. 40 2.6.1. Cải thiện thuật toán tìm đường đi ngắn nhất từ hai hướng ............... 40 5 2.6.2. Song song hóa truy vấn tìm đường đi ngắn nhất .............................. 41 2.7. Tổng kết chương ...................................................................................... 41 Chương 3: Thực nghiệm và đánh giá.................................................................. 42 3.1. Cài đặt ...................................................................................................... 42 3.2. Thực nghiệm ............................................................................................ 46 3.2.1. Cuộc thi ACM Sigmod Contest 2016 ............................................... 46 3.2.2. Kiểm nghiệm với bộ dữ liệu SNAP .................................................. 47 3.3. Tổng kết chương ...................................................................................... 53 Kết luận chung .................................................................................................... 54 Các đóng góp chính ........................................................................................ 54 Hướng phát triển ............................................................................................. 54 Danh mục công trình khoa học của tác giả ......................................................... 55 Tài liệu tham khảo .............................................................................................. 56 6 DANH MỤC CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮT Kí hiệu Giải thích Tiếng Anh Tiếng Việt GPS Global Positioning System Hệ thống định vị toàn cầu ACM Association for Computing Machinery Hiệp hội máy tính thế giới Sigmod Special Interest Group on Management of Data Nhóm quan tâm đặc biệt về quản lý dữ liệu DFS Depth First Search Thuật toán duyệt đồ thị theo chiều sâu BFS Breadth First Search Thuật toán duyệt đồ thị theo chiều rộng BBFS Bi-directional Breadth First Search Thuật toán duyệt đồ thị theo chiều rộng từ cả hai hướng. SNAP Stanford Network Analysis Platform Nền tảng phân tích mạng của Stanford 7 DANH MỤC CÁC BẢNG Bảng 1.1: Một số thống kê về độ phức tạp một số phương phức cơ bản trong đồ thị [11] ......................................................................................................... 17 Bảng 2.1: Độ trễ trong bộ nhớ 2016 ................................................................... 34 Bảng 3.1:Thống kê bộ dữ liệu ACM Sigmod ..................................................... 46 Bảng 3.2: Kết quả cuộc thi ACM Sigmod (tính theo giây) ................................ 46 Bảng 3.3: Thống kê bộ dữ liệu LiveJournal và Pokec ........................................ 49 Bảng 3.4: Kết quả thử nghiệm (tính theo mili giây) ........................................... 51 8 DANH MỤC CÁC HÌNH VẼ Hình 1.1: Mạng xã hội ........................................................................................ 10 Hình 1.2: Đường đi trong mạng xã hội ............................................................... 11 Hình 1.3: Chu trình trong mạng xã hội ............................................................... 11 Hình 1.4: Bản đồ khoảng cách một số tỉnh thành phía Bắc ................................ 12 Hình 1.5: Mạng xã hội có hướng ........................................................................ 12 Hình 1.6: Đồ thị .................................................................................................. 13 Hình 1.7: Đồ thị có hướng .................................................................................. 15 Hình 2.1: Dữ liệu đầu vào ................................................................................... 29 Hình 2.2: Lô dữ liệu kiểm thử............................................................................. 29 Hình 2.3: Giới thiệu về OpenMP ........................................................................ 31 Hình 2.4: Giới thiệu về Pthread .......................................................................... 32 Hình 2.5: Song song hóa truy vấn bởi Cilk Plus................................................. 33 Hình 2.6: Cấu trúc dữ liệu của đồ thị .................................................................. 36 Hình 2.7: Thêm một cạnh bằng cách chèn vào giữa mảng ................................. 37 Hình 2.8: Cấu trúc dữ liệu danh sách kề cấp phát trước khoảng trống ............... 38 Hình 2.9: Thêm một cạnh bằng cách cấp trước khoảng trống ............................ 38 Hình 2.10: Quá trình thêm một cạnh .................................................................. 39 Hình 2.11: Quá trình xóa một cạnh ..................................................................... 39 Hình 2.12: Thứ tự duyệt đỉnh trong thuật toán duyệt đồ thị theo chiều rộng từ hai hướng .......................................................................................................... 40 Hình 3.1: Thời gian thực thi giữa hai phép toán thao tác trên mảng và bit ........ 45 Hình 3.2: Kết quả cuộc thi ACM Sigmod 2016.................................................. 48 Hình 3.3: Kết quả thử nghiệm với bộ dữ liệu SIGMOD TEST .......................... 52 Hình 3.4: Kết quả thử nghiệm với bộ dữ liệu POKEC ....................................... 52 Hình 3.5: Kết quả thử nghiệm với bộ dữ liệu LIVEJOURNAL ......................... 53 9 Giới thiệu chung Động lực nghiên cứu Hiện nay, chúng ta đang sống trong thời đại bùng nổ về công nghệ thông tin cũng như bùng nổ về xã hội mạng. Một số mạng điển hình như mạng xã hội (Facebook, Twitter), mạng sinh học, mạng phân tán nội dung, mạng lưới giao thông, mạng thông tin… có số lượng dữ liệu tăng nhanh chóng mặt. Để giải quyết những thách thức về mặt dữ liệu lớn trên, có rất nhiều phương pháp tiếp cận, trong đó phương pháp tiếp cận dựa trên đồ thị được cho là trực quan và phù hợp nhất [8]. Với việc sử dụng lý thuyết đồ thị, các đỉnh biểu diễn các thực thể và các cạnh biểu diễn mối liên hệ giữa chúng. Trong đồ thị, tìm đường đi (ngắn nhất) là vấn đề tìm sự kết nối giữa hai đỉnh của một đồ thị và đảm bảo đường đi đó là ngắn nhất dựa trên một số yêu cầu cho trước. Đây là vấn đề nền tảng và cơ bản được áp dụng trong rất nhiều ứng dụng thực tế như tìm đường đi ngắn nhất giữa hai địa điểm sử dụng GPS hay tìm mối liên kết giữa hai người trên mạng xã hội [6]. Vấn đề này bình thường rất đơn giản, nhưng trong bối cảnh số lượng các đỉnh, cạnh của đồ thị rất lớn (vài triệu đỉnh) và thay đổi nhanh (thêm cạnh, bớt cạnh), làm thế nào để tối ưu hóa quá trình tìm đường đi ngắn nhất là một thách thức lớn [21]. Mục tiêu và nội dung chính của luận văn Với mục tiêu trên, luận văn này sẽ trình bày giải pháp để cải thiện hiệu năng quá trình tối ưu truy vấn trên đồ thị động, quy mô lớn có hướng và không trọng số. Phương pháp tối ưu dựa trên các ý tưởng: cấu trúc dữ liệu phù hợp, tối ưu không gian tìm kiếm và cài đặt phù hợp. Tổ chức luận văn Nội dung của luận văn sẽ được tổ chức như sau: Mở đầu: Đặt vấn đề Chương 1: Giới thiệu về cơ sở lý thuyết, các vấn đề liên quan đến đồ thị và bài toán tìm đường đi ngắn nhất trong đồ thị. Chương 2: Trình bày bài toán, cách tiếp cận, phương pháp giải quyết bài toán. Chương 3: Thực nghiệm và đánh giá các kết quả đạt được. Kết luận chung: Kết luận và đưa ra hướng phát triển tiếp theo. 10 Chương 1: Cơ sở lý thuyết và các vấn đề liên quan 1.1. Đồ thị Trước khi tìm hiểu về lý thuyết đồ thị, chúng ta cùng xét một ví dụ về một mạng xã hội nhỏ [7] sau: Hình 1.1: Mạng xã hội Mỗi ô màu xanh biểu diễn cho một người dùng trong mạng xã hội, giữa hai người có một đường liên kết với nhau có nghĩa là họ biết nhau. Ngược lại, nếu không có đường liên kết này thì họ không biết nhau. Mối liên hệ “biết nhau” trong đồ thị này là hai chiều. Ví dụ: An biết Thanh thì Thanh sẽ biết An. Một mạng xã hội như thế này là ví dụ cơ bản về đồ thị. Tên người chính là các đỉnh, và mỗi đường liên kết giữa hai người chính là các cạnh. Chúng ta thường biểu diễn sự liên kết giữa hai đỉnh u và v bởi cặp (u, v). Bởi vì quan hệ “biết nhau” ở đây là quan hệ hai chiều, nên đây là ví dụ của đồ thị vô hướng. Trong đồ thị vô hướng, cạnh (u, v) tương tự như cạnh (v, u). Trong đồ thị có hướng, quan hệ “biết nhau” không còn là hai chiều nữa, một người A biết người B nhưng chưa chắc người B đã biết người A. Trong đồ thị vô hướng, một cạnh nối giữa hai đỉnh thì cạnh này gọi là liên thuộc đến hai đỉnh đó. Chúng ta gọi các đỉnh liên kết với nhau bằng một cạnh là các đỉnh liền kề hoặc hàng xóm của nhau. Số lượng cạnh liên thuộc của một đỉnh là bậc của đỉnh đó. Nhìn trên đồ thị, An và Sơn sẽ không biết nhau. Giả sử rằng Sơn muốn làm quen với An. Có cách nào để Sơn làm quen với An không? Nhìn trên đồ thị ta thấy, Sơn biết Hạnh và Hạnh lại biết Linh, cuối cùng Linh biết An. Vậy Sơn có thể thông qua Hạnh và Linh để làm quen với An. Thực ra, đây là một đường đi trong đồ thị, đường đi đi từ điểm đầu Sơn đến điểm cuối An. Không có đường đi 11 ngắn hơn giữa Sơn và An mà phải đi qua ít nhất hai người. Đường đi giữa hai đỉnh như thế này được gọi là đường đi ngắn nhất. Chúng ta đánh dấu đường đi ngắn nhất này như Hình 1.2. Hình 1.2: Đường đi trong mạng xã hội Khi đường đi xuất phát từ một đỉnh và quay lại chính nó, chúng ta gọi đó là một chu trình. Mạng xã hội bao gồm rất nhiều chu trình. Ví dụ từ An, Bình tới Cường, Linh rồi cuối cùng quay lại An. Thực ra, có chu trình ngắn hơn đó là từ An qua Bình tới Linh rồi quay lại An. Hình 1.3: Chu trình trong mạng xã hội Có những lúc, chúng ta thêm các trọng số vào các cạnh. Ví dụ, trong mạng xã hội, chúng ta có thể sử dụng một trọng số để xác định mức độ biết nhau giữa hai người. Một ví dụ cụ thể khác về đồ thị chính là bản đồ đường đi. Giả sử tất cả đều là đường hai chiều, thì bản đồ đường đi này cũng là một đồ thị vô hướng, với các thành phố (địa điểm) là đỉnh, các đường đi là cạnh, giá trị trọng số chính là số biểu diễn khoảng cách giữa các thành phố. Ví dụ Hình 1.4 mô tả khoảng cách giữa một số tỉnh thành phía Bắc nước Việt Nam . 12 Hình 1.4: Bản đồ khoảng cách một số tỉnh thành phía Bắc Cách thức đơn giản biểu diễn trọng số là ta viết thêm một số thực lên cạnh của đồ thị. Khi đó, đồ thị có các cạnh có trọng số như thế này được gọi là đồ thị có trọng số. Trong trường hợp bản đồ đường đi, nếu chúng ta muốn tìm đường đi ngắn nhất giữa các vị trí, chúng ta phải tìm kiếm đường đi qua các vị trí trung gian sao cho tổng trọng số là nhỏ nhất. Đây chính là bài toán tìm đường đi ngắn nhất giữa hai đỉnh trong đồ thị. Ví dụ ở bản đồ Hình 1.4, đường đi ngắn nhất từ Hà Nội tới Hạ Long, sẽ qua Hải Dương, Hải Phòng. Tổng cộng đoạn đường đi này có chiều dài 163km. Mối quan hệ giữa hai đỉnh không phải lúc nào cũng là hai chiều. Lấy ví dụ, trong bản đồ đường đi, chúng ta có thể gặp đường đi một chiều. Để biểu diễn sự có hướng này, các cạnh được thêm dấu mũi tên ở cuối và đồ thị này được gọi là đồ thị có hướng. Ví dụ Hình 1.5 mô tả một mạng xã hội có hướng. Mũi tên có hướng chỉ từ An sang Linh có nghĩa là An biết Linh, nhưng ngược lại Linh không biết An. Dễ nhận thấy, đồ thị ở Hình 1.5 không có chu trình, khi đó đồ thị được gọi là có hướng không chu trình. Hình 1.5: Mạng xã hội có hướng 13 Chúng ta có thể sử dụng các thuật ngữ khác trong đồ thị có hướng. Ví dụ, một cạnh có hướng sẽ ra ở một đỉnh và vào một đỉnh khác. Nếu cạnh đó ra ở đỉnh u và vào một đỉnh v, sẽ được kí hiệu là (u, v), và thứ tự này sẽ cho ta biết hướng đi từ đỉnh nào đến nào. Tổng số cạnh ra của một đỉnh gọi là bậc ra, tổng số cạnh vào của một đỉnh gọi là bậc vào. Như chúng ta thấy, đồ thị có rất nhiều ứng dụng trong biểu diễn các sự vật, mối quan hệ giữa các sự vật đó trong thế giới thực. Phần tiếp theo, luận văn sẽ trình bày một số lý thuyết nền tảng về đồ thị. 1.1.1. Giới thiệu đồ thị Đồ thị (G), kí hiệu là G = (V, E) bao gồm một tập các đỉnh (V) và tập các cạnh (E). Trong đó mỗi cạnh E nối giữa hai đỉnh thuộc tập các đỉnh (V) và được kí hiệu là E = (u, v) (Đỉnh u nối đỉnh v). Ví dụ về đồ thị được đưa ra ở Hình 1.6. Hình 1.6: Đồ thị Đồ thị được phân loại dựa vào đặc điểm của các cạnh như sau: Đơn đồ thị vô hướng Đơn đồ thị vô hướng G = (V, E) bao gồm V là tập các đỉnh, và E là tập các cặp không có thứ tự gồm hai phần tử khác nhau của V được gọi là cạnh [1]. Đa đồ thị vô hướng Đa đồ thị vô hướng G = (V, E) bao gồm V là tập các đỉnh, và E là họ các cặp không có thứ tự gồm hai phần tử khác nhau của V gọi là các cạnh. Hai cạnh e1 và e2 được gọi là cạnh lặp nếu chúng cùng tương ứng với một cặp đỉnh [1]. Thực tế, mỗi đơn đồ thị đều là đa đồ thị, nhưng không phải đa đồ thị nào cũng là đơn đồ thị, vì trong đa đồ thị có thể có hai (hoặc nhiều hơn) cạnh nối một cặp đỉnh nào đó. Giả đồ thị vô hướng Giả đồ thị vô hướng G = (V, E) bao gồm V là một tập các đỉnh, và E là họ các cặp không có thứ tự gồm hai phần tử (không nhất thiết phải khác nhau) của V gọi là các cạnh. Cạnh e được gọi là khuyên nếu nó có dạng e = (u, u) [1]. 14 Từ đó, với tính chất có hướng của đồ thị được định nghĩa như sau: Đơn đồ thị có hướng Đơn đồ thị có hướng G = (V, E) bao gồm V là một tập các đỉnh, và E là tập các cặp có thứ tự gồm hai phần tử của V được gọi là cung. Đa đồ thị có hướng Đa đồ thị có hướng G = (V, E) bao gồm V là tập đỉnh, E là họ các cặp có thứ tự gồm hai phần tử khác nhau của V được gọi là các cung. Hai cung e1 và e2 được gọi là cung lặp nếu chúng cùng tương ứng với một cặp đỉnh. 1.1.2. Một số thuật ngữ cơ bản Bậc của đỉnh Hai đỉnh u và v của đồ thị vô hướng G = (V, E) được gọi là kề nhau nếu (u, v) là cạnh thuộc đồ thị G. Nếu e = (u, v) là cạnh của đồ thị G thì ta nói cạnh này liên thuộc với hai đỉnh u và v, hoặc ta nói cạnh e nối đỉnh u với đỉnh v, đồng thời các đỉnh u và v sẽ được gọi là đỉnh đầu mút của cạnh e. Bậc của đỉnh v trong đồ thị G = (V, E) ký hiệu deg(v) là số các cạnh liên thuộc với nó, riêng khuyên tại một đỉnh được tính hai lần cho bậc của nó. Đỉnh v gọi là đỉnh treo nếu deg(v) = 1 và gọi là đỉnh cô lập nếu deg(v) = 0. Ví dụ: đồ thị vô hướng G = (V, E) ở Hình 1.6. + V = {1,2,3,4,5,6}. + E = {(1,2), (1,3), (1,4), (2,3), (2,4), (2,5)}. + Bậc của các đỉnh: deg(1)=3; deg(2)=4, deg(3)=2, deg(4)=2, deg(5)=1, deg(6)=0. + Đỉnh 5 là đỉnh treo. + Đỉnh 6 là đỉnh cô lập. Trong đồ thị có hướng, bậc của đỉnh v được chia ra thành bậc trong (Incoming Nodes) và bậc ngoài (Outgoing Nodes). Bậc trong của đỉnh v là số lượng các cạnh được nối tới đỉnh v, kí hiệu là deg+(v). Bậc ngoài của đỉnh v là số lượng các cạnh được nối từ đỉnh v, kí hiệu là deg-(v). Đường đi và chu trình, đồ thị liên thông Trong đồ thị vô hướng, đường đi độ dài n từ đỉnh u đến đỉnh v, trong đó n là số nguyên dương trên đồ thị vô hướng G = (V, E) là dãy 15 x0, x1, …, xn-1, xn Trong đó u = x0, v = xn, (xi, xi+1) ∈ E, i = 0, 1, 2, ...., n-1 Đường đi nói trên còn có thể biểu diễn dưới dạng dãy các cạnh: (x0, x1), (x1, x2), ..., (xn-1, xn) Đỉnh u gọi là đỉnh đầu, còn đỉnh v gọi là đỉnh cuối của đường đi. Đường đi có đỉnh đầu trùng với đỉnh cuối (tức là u = v) được gọi là chu trình. Đường đi hay chu trình được gọi là đơn nếu như không có cạnh nào bị lặp [1]. Khái niệm đường đi và chu trình trên đồ thị có hướng được định nghĩa hoàn toàn tương tự như trường hợp đồ thị vô hướng, chỉ khác là chúng ta phải chú ý đến hướng trên các cung [1]. Đồ thị vô hướng G = (V, E) được gọi là liên thông nếu luôn tìm được đường đi giữa hai đỉnh bất kỳ của nó. 1.1.3. Biểu diễn đồ thị Trong phần này, luận văn sẽ giới thiệu bốn cấu trúc dữ liệu chính dùng để biểu diễn một đồ thị. Trong mỗi cấu trúc, phần biểu diễn các đỉnh được giữ nguyên, tuy nhiên phần biểu diễn các cạnh lại hoàn toàn khác nhau. Đồ thị ở Hình 1.7 được sử dụng cho toàn bộ ví dụ trong mục 1.1.3 này. Hình 1.7: Đồ thị có hướng Danh sách cạnh (Edge list) Trong biểu diễn đồ thị theo danh sách các cạnh, tất cả các cạnh e thuộc E đều được lưu dưới dạng hai phần tử (vi, vj) trong danh sách lưu trữ. Nếu cạnh có trọng số, chúng ta cần thêm một phần tử thứ ba vào trong mảng. Mỗi cạnh sẽ bao gồm hai hoặc ba số, vậy nên không gian để lưu trữ đồ thị theo danh sách cạnh là Θ(|E|). Ví dụ: L= {(1,2), (1,3), (1,4), (2,3), (2,4)} 16 Danh sách kề (Adjacency list) Trong biểu diễn đồ thị bằng danh sách kề, với mỗi đỉnh u, ta lưu trữ tất cả các đỉnh v kề với nó. Và chúng ta có tất cả |V| danh sách kề nhau như thế này, một đỉnh và một danh sách các nốt kề với đỉnh, vậy nên không gian để lưu trữ đồ thị theo cách này là Θ(|V|+|E|). Ví dụ: Đỉnh Danh sách kề 1 {2, 3,4} 2 {3,4} 3 {} 4 {} Ma trận liên thuộc (Incidence matrix) Ma trận liên thuộc đỉnh – cạnh của đồ thị G = (V, E) là một đồ thị |V| x |E|, trong đó phần tử ở hàng thứ i và cột thứ j bằng 1 khi và chỉ i là đỉnh đầu của cung thứ j, bằng -1 khi và chỉ khi i là đỉnh cuối của cung thứ j và bằng 0 trong trường hợp còn lại. Đồ thị được tổ chức theo kiểu này sẽ tốn không gian lưu trữ là Θ(|V| x |E|). Ví dụ: 1 2 3 4 (1,2) (1,3) (1,4) (2,3) (2,4) 1 −1 0 0 1 0 −1 0 1 0 0 −1 0 1 −1 0 0 1 0 −1 Ma trận kề (Adjaceny matrix) Ma trận kề của đồ thị G = (V, E) là một đồ thị |V| x |V|, trong đó phần tử ở hàng thứ i và cột thứ j bằng 1 khi và chỉ khi tồn tại cung (i, j) trong đồ thị, bằng 0 trong trường hợp ngược lại. Đồ thị được tổ chức theo kiểu này sẽ tốn không gian lưu trữ là Θ(|V|2). 17 Ví dụ: 0 0 + = 0 0 1 0 0 0 1 1 0 0 1 1 0 0 Một số thống kê về độ phức tạp thuật toán một số phương phức cơ bản của các cấu trúc dữ liệu được trình bày ở Bảng 1.1. Giả sử rằng n là số đỉnh, m là số cạnh, dv là bậc của đỉnh v. Bảng 1.1: Một số thống kê về độ phức tạp một số phương phức cơ bản trong đồ thị [11] Phương thức Danh sách Danh sách Ma trận Ma trận kề cạnh kề liên thuộc numVertices( ) Trả về số lượng đỉnh của đồ thị. O(1) O(1) O(1) O(1) O(1) O(1) O(1) O(1) O(n) O(n) O(n) O(n) O(m) O(m) O(m) O(m) O(m) O(min(du , dv)) O(m) O(1) numVertices( ) Trả về số lượng cạnh của đồ thị. vertices( ) Trả về phép duyệt tất cả các đỉnh của đồ thị. edges( ) Trả về phép duyệt tất cả các cạnh của đồ thị. getEdge(u, v) Kiểm tra xem cạnh (u, v) có tồn tại không? 18 outDegree(v) inDegree(v) Trả về số lượng đỉnh vào và đỉnh ra của nốt v. O(m) O(1) O(m) O(n) O(m) O(dv ) O(m) O(n) O(1) O(1) O(m×n) O(n2) O(m) O(dv) O(m×n) O(n2) O(1) O(1) O(1) O(1) O(1) O(1) O(1) O(1) Θ(n) Θ(m+n) Θ(m×n) Θ(n2) outgoingEdges(v) incomingEdges(v) Trả về phép duyệt tất cả đỉnh vào và đỉnh ra của nốt v. insertVertex(x) Thêm một đỉnh mới vào đồ thị. removeVertex(v) Xóa một đỉnh trong đồ thị. insertEdge(u, v) Thêm một cạnh mới vào đồ thị. removeEdge(u, v) Xóa một cạnh trong đồ thị. Không gian lưu trữ 1.1.4. Các thuật toán tìm kiếm trên đồ thị và ứng dụng Trong đồ thị, bài toán duyệt qua tất cả các đỉnh của đồ thị sao cho mỗi đỉnh chỉ thăm đúng duy nhất một lần là một bài toán quan trọng thu hút sự quan tâm nghiên cứu của rất nhiều các nhà khoa học. Trong mục này, luận văn sẽ trình bày hai thuật toán duyệt đồ thị cơ bản: thuật toán tìm kiếm theo chiều sâu (Depth First 19 Search – DFS) và thuật toán tìm kiếm theo chiều rộng (Breadth First Seach – BSF). Trên cơ sở hai thuật toán cơ bản này, chúng ta có thể áp dụng chúng để giải quyết một số bài toán quan trọng của lý thuyết đồ thị. Thuật toán tìm kiếm theo chiều sâu (DFS) Ý tưởng cơ bản của thuật toán tìm kiếm theo chiều sâu là bắt đầu từ một đỉnh v nào đó của đồ thị, chọn một đỉnh bất kỳ kề với v và lặp lại quá trình đối với đỉnh được chọn này. Nếu như trong số các đỉnh kề với v tìm được đỉnh w là chưa được xét thì ta sẽ xét đỉnh này và bắt đầu từ đó chúng ta tiếp tục quá trình tìm kiếm. Còn nếu không còn đỉnh nào kề với v chưa được xét thì có nghĩa là đỉnh này đã được duyệt xong và chúng ta sẽ quay trở lại tiếp tục tiếp tục duyệt từ đỉnh mà trước đó chúng ta chưa duyệt. Có thể tóm tắt lại là tìm kiếm theo chiều sâu bắt đầu từ đỉnh v được thực hiện trên cơ sở tìm kiếm theo chiều sâu từ tất các đỉnh chưa xét kề với v. Quá trình này có thể mô tả bởi thủ tục đệ quy sau đây: DFS(v) { // Tìm kiếm theo chiều sâu bắt đầu từ đỉnh v visit(v); check[v] = false; For u ∈ neighbor (v) do If check[u] then DFS(u); } Khi đó, duyệt đồ thị theo chiều sâu được thực hiện nhờ thuật toán sau: for v ∈ V do check[v] = TRUE; //thiết lập giá trị ban đầu cho mảng check[]*/ for v ∈ V do if (check[v]) DFS(i); Để đánh giá độ phức tạp của thuật toán tìm kiếm theo chiều sâu trên đồ thị, trước hết nhận thấy rằng số phép toán cần thực hiện trong hai vòng lặp for của thuật toán là cỡ n. Thủ tục DFS phải thực hiện trong trường hợp xấu nhất là n lần. Tổng số phép toán cần phải thực hiện trong các thủ tục này là O(n+m), do trong thủ tục ta phải xét qua tất cả các cạnh và các đỉnh của đồ thị. Vậy độ phức tạp tính toán của thuật toán là O(n+m) [1]. Thuật toán tìm kiếm theo chiều rộng (BFS) Trong thuật toán tìm kiếm theo chiều sâu, đỉnh được thăm càng muộn sẽ càng sớm trở thành đỉnh đã duyệt xong. Điều đó là hệ quả tất yếu bởi vì các đỉnh